oj.uz

Submission #235610

# Submission time Handle Problem Language Result Execution time Memory
235610 2020-05-28T20:03:18 Z Dremix10 Crayfish scrivener (IOI12_scrivener) C++17
5 / 100
 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

scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:47:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^

Subtask #1
5.0 / 5.0

# 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

Subtask #2
0 / 7.0

# 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 -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 119420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 102496 KB Output isn't correct
2 Halted 0 ms 0 KB -