oj.uz

Submission #235612

# Submission time Handle Problem Language Result Execution time Memory
235612 2020-05-28T20:06:51 Z Dremix10 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 629 ms 145632 KB 
#include <bits/stdc++.h>
using namespace std;
#define N (int)1e6+1
#define maxp 22

struct ano{

char c;
int sons[26];

};

ano trie[N+1];
int curr=0;
int t=1;
int lift[N+1][maxp];
int googleChrome[N+1];
int d[N+1];
int cnt=1;

void Init() {

}

void TypeLetter(char c) {
    int next=trie[curr].sons[c-'a'];
    if(next==0){
        trie[curr].sons[c-'a']=cnt;
        d[cnt]=d[curr]+1;

        trie[cnt].c=c;
        lift[cnt][0]=curr;
        curr=cnt;
        int i;
        for(i=1;i<maxp;i++)
            lift[curr][i]=lift[lift[curr][i-1]][i-1];
        cnt++;
    }
    else
        curr=next;

    googleChrome[t++]=curr;
   // cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}

void UndoCommands(int n) {
    curr=googleChrome[t-n-1];
   // int i;
  //  for(i=1;i<t;i++)
  //      cout<<googleChrome[i]<<" ";
  //  cout<<endl;
    googleChrome[t++]=curr;
    //cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}

char GetLetter(int x) {
    //cout<<d[curr]<<" "<<curr<<endl;
    int k=d[curr]-x-1;
    int i;
    int ans=curr;
    for(i=maxp-1;i>=0;i--)
    if(k>=(1<<i)){
        k-=(1<<i);
        ans=lift[ans][i];
    }
  //  cout<<ans<<endl;
    return trie[ans].c;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 6 ms 640 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 116008 KB Output is correct
2 Correct 480 ms 131248 KB Output is correct
3 Correct 421 ms 128480 KB Output is correct
4 Correct 412 ms 98680 KB Output is correct
5 Correct 455 ms 111864 KB Output is correct
6 Correct 377 ms 141632 KB Output is correct
7 Correct 398 ms 70984 KB Output is correct
8 Correct 388 ms 106488 KB Output is correct
9 Correct 485 ms 145632 KB Output is correct
10 Correct 283 ms 106732 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 98116 KB Output is correct
2 Correct 629 ms 91256 KB Output is correct
3 Correct 404 ms 98300 KB Output is correct
4 Correct 413 ms 72528 KB Output is correct
5 Correct 370 ms 108408 KB Output is correct
6 Correct 398 ms 101168 KB Output is correct
7 Correct 397 ms 108152 KB Output is correct
8 Correct 486 ms 53496 KB Output is correct
9 Correct 578 ms 94568 KB Output is correct
10 Correct 308 ms 105896 KB Output is correct