# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
235610 | 2020-05-28T20:03:18 Z | Dremix10 | Crayfish scrivener (IOI12_scrivener) | C++17 | 494 ms | 119420 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]; } 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 304 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Incorrect | 5 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 640 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 415 ms | 119420 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 494 ms | 102496 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |