oj.uz

Submission #157766

# Submission time Handle Problem Language Result Execution time Memory
157766 2019-10-12T20:03:22 Z davitmarg Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 839 ms 94968 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1000000;
int k, n, up[N + 10][30], d[N + 10], ind[N + 10], v = 1, timer;
char a[N + 10];

void addNode(int p, char x)
{
    v = ++n;
    a[v] = x;
    d[v] = d[p] + 1;
    up[v][0] = p;
    for (int i = 1; i <= k; i++)
        up[v][i] = up[up[v][i - 1]][i - 1];
}

char get(int v, int cnt)
{
    if (cnt == d[v])
        return a[v];
    for (int i = k; i >= 0; i--)
    {
        int p = up[v][i];
        if (d[p] > cnt)
            v = p;
    }
    return a[up[v][0]];
}

void Init()
{
    while ((1 << k) <= N)
        k++;
}

void TypeLetter(char x)
{
    addNode(v, x);
    ind[++timer] = v;
}

char GetLetter(int pos)
{
    return get(v, pos + 1);
}

void UndoCommands(int cnt)
{
    v = ind[timer + 1] = ind[timer - cnt];
    timer++;
}

#ifdef death

int main()
{
    Init();
    TypeLetter('a');
    TypeLetter('b');
    TypeLetter('c');
    cout << GetLetter(2) << endl;
    TypeLetter('d');
    UndoCommands(2);
    UndoCommands(1);
    cout << GetLetter(2) << endl;
    return 0;
}

#endif

/*
 
 
 
  
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 408 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 4 ms 636 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 74464 KB Output is correct
2 Correct 563 ms 85820 KB Output is correct
3 Correct 442 ms 84976 KB Output is correct
4 Correct 461 ms 69624 KB Output is correct
5 Correct 626 ms 74312 KB Output is correct
6 Correct 473 ms 92796 KB Output is correct
7 Correct 489 ms 48180 KB Output is correct
8 Correct 474 ms 70136 KB Output is correct
9 Correct 817 ms 94968 KB Output is correct
10 Correct 250 ms 69780 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 63248 KB Output is correct
2 Correct 813 ms 60876 KB Output is correct
3 Correct 446 ms 66488 KB Output is correct
4 Correct 487 ms 51596 KB Output is correct
5 Correct 443 ms 71672 KB Output is correct
6 Correct 414 ms 67456 KB Output is correct
7 Correct 531 ms 71828 KB Output is correct
8 Correct 622 ms 37084 KB Output is correct
9 Correct 839 ms 62720 KB Output is correct
10 Correct 244 ms 69344 KB Output is correct