oj.uz

Submission #116193

# Submission time Handle Problem Language Result Execution time Memory
116193 2019-06-11T08:39:58 Z Mercenary Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 829 ms 180092 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;

const int maxn = 1e6 + 5;
const int logn = log2(maxn) + 1;

template<class T = char>
struct node{
    node* pre[logn];
    T val;
    int len;
    node(){
//        cout << 1;
        for(int j = 0 ; j < logn ; ++j)pre[j] = 0;
        len = 0;
    }
    void add(node* par , T val){
        len = par->len + 1;
        this->val = val;
        pre[0] = par;
//        cout << pre[0] << endl;
        for(int j = 1 ; j < logn ; ++j){
            if(pre[j - 1])pre[j] = pre[j - 1]->pre[j - 1];
            else break;
        }
    }
    T GetValAt(int pos){
        pos = len - pos - 1;
        node* now = this;
//        cout << now << endl;
        for(int j = 0 ; j < logn ; ++j){
            if((pos >> j) & 1)now = now->pre[j];
        }
//        cout << now << endl;
        return now->val;
    }
};
node<char> preorder[maxn];
node<char>* a[maxn];

int now = 0;

void Init() {
    for(int i = 0 ; i < maxn ; ++i)a[i] = &preorder[i];
}

void TypeLetter(char L) {
    ++now;
    a[now]->add(a[now - 1] , L);
}

void UndoCommands(int U) {
    ++now;
    a[now] = a[now - U - 1];
}

char GetLetter(int P) {
    return a[now]->GetValAt(P);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 172536 KB Output is correct
2 Correct 120 ms 172536 KB Output is correct
3 Correct 125 ms 172536 KB Output is correct
4 Correct 122 ms 172792 KB Output is correct
5 Correct 121 ms 172540 KB Output is correct
6 Correct 122 ms 172536 KB Output is correct
7 Correct 122 ms 172536 KB Output is correct
8 Correct 147 ms 172512 KB Output is correct
9 Correct 146 ms 172552 KB Output is correct
10 Correct 122 ms 172540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 172536 KB Output is correct
2 Correct 120 ms 172472 KB Output is correct
3 Correct 122 ms 172536 KB Output is correct
4 Correct 121 ms 172520 KB Output is correct
5 Correct 121 ms 172508 KB Output is correct
6 Correct 122 ms 172608 KB Output is correct
7 Correct 121 ms 172556 KB Output is correct
8 Correct 133 ms 172536 KB Output is correct
9 Correct 121 ms 172600 KB Output is correct
10 Correct 118 ms 172536 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 172640 KB Output is correct
2 Correct 122 ms 172620 KB Output is correct
3 Correct 120 ms 172536 KB Output is correct
4 Correct 119 ms 172536 KB Output is correct
5 Correct 120 ms 172508 KB Output is correct
6 Correct 131 ms 172664 KB Output is correct
7 Correct 162 ms 172536 KB Output is correct
8 Correct 135 ms 172560 KB Output is correct
9 Correct 123 ms 172692 KB Output is correct
10 Correct 120 ms 172668 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 176464 KB Output is correct
2 Correct 770 ms 176764 KB Output is correct
3 Correct 479 ms 177544 KB Output is correct
4 Correct 473 ms 179192 KB Output is correct
5 Correct 634 ms 177888 KB Output is correct
6 Correct 582 ms 177016 KB Output is correct
7 Correct 659 ms 178936 KB Output is correct
8 Correct 725 ms 178040 KB Output is correct
9 Correct 828 ms 177264 KB Output is correct
10 Correct 268 ms 176632 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 177464 KB Output is correct
2 Correct 751 ms 178708 KB Output is correct
3 Correct 469 ms 178424 KB Output is correct
4 Correct 469 ms 180092 KB Output is correct
5 Correct 562 ms 177652 KB Output is correct
6 Correct 537 ms 177404 KB Output is correct
7 Correct 518 ms 177352 KB Output is correct
8 Correct 753 ms 179216 KB Output is correct
9 Correct 829 ms 178888 KB Output is correct
10 Correct 269 ms 176776 KB Output is correct