Fişierul intrare/ieşire:kthvalue.in, kthvalue.outSursăHappy Birthday Infoarena 2014
AutorAdrian BudauAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test3.3 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kthvalue

Aveti o problema foarte simpla de rezolvat. Vi se da un sir (initial vid) si multe operatii pe el.

Operatiile sunt de 5 tipuri:

  • Tipul 1, se adauga pe pozitia 1 valoarea v, celelalate elemente deplasandu-se cu 1 la dreapta.
  • Tipul 2, se adauga la final valoarea v
  • Tipul 3, se sterge primul element, iar restul se deplaseaza cu 1 la stanga, inversa operatiei de tip 1
  • Tipul 4, se sterge ultimul element, inversa operatiei de tip 2
  • Tipul 5, vi se dau un x, y si un k. Trebuie sa spuneti care este al k-lea element in ordinea sortarii printre elemente aflate pe pozitiile x, x + 1, x + 2, ..., y din sir.

Date de intrare

Fişierul de intrare kthvalue.in va contine pe prima linia un numar natural M, reprezentand numarul de operatii pe care trebuie sa le sustineti.
Urmatoarele M linii vor descrie fiecare operatie in parte. Astfel primul numar de pe fiecare linie va reprezenta tipul operatiei (1 2 3 4 sau 5).

  • Pentru operatiile de tip 1 pe acelasi rand se va mai afla un numar v reprezentand valoarea ce va fi adaugata.
  • Pentru operatiile de tip 5 pe acelasi rand se vor mai afla 3 numere x, y si k cu descrierile de mai sus.
Pentru a parsa fisierul puteti folosi urmatorul cod in C++
#include <fstream>
#include <memory>
 
using namespace std;
 
class Reader {
  public:
    Reader(const string& filename):
            m_stream(filename),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
        next();
    }
 
    Reader& operator>>(int& value) {
        value = 0;
        while (current() < '0' || current() > '9')
            next();
        while (current() >= '0' && current() <= '9') {
            value = value * 10 + current() - '0';
            next();
        }
        return *this;
    }
 
  private:
    const int kBufferSize = 32768;
 
    char current() {
        return m_buffer[m_pos];
    }
 
    void next() {
        if (!(++m_pos != kBufferSize)) {
            m_stream.read(m_buffer.get(), kBufferSize);
            m_pos = 0;
        }
    }
 
    ifstream m_stream;
    int m_pos;
    unique_ptr<char[]> m_buffer;
};
 
Reader fin("kthvalue.in"); int x; fin >> x;

Date de ieşire

În fişierul de ieşire kthvalue.out trebuie sa se afle atatea linii cate operatii de tip 5 sunt. Pentru fiecare trebuie sa afisati numarul corespunzator.

Restricţii

  • 1 ≤ M ≤ 1.000.000
  • 1 ≤ x ≤ y ≤ numarul de elemente din sir la momentul respectiv
  • 1 ≤ v ≤ M
  • Nu vor fi operatii de tip 3 sau 4 cand sirul este vid
  • Vi se recomanda sa parsati fisierul de intrare..

Exemplu

kthvalue.inkthvalue.out
7
1 1
1 7
2 7
5 1 3 1
3
2 6
5 2 3 2
1
7

Explicaţie

Sirul va arata asa in urma transformarilor [] -> [1] -> [7 1] -> [7 1 7] -> [1 7] -> [1 7 6]

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?