oj.uz

Submission #409641

# Submission time Handle Problem Language Result Execution time Memory
409641 2021-05-21T09:15:26 Z pliam Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 414 ms 151624 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define MAXL 25//max logN

int up[MAXL][MAXN];
vector<int> ver_node;
int trie[MAXN][26];
char let[MAXN];//letter
int len[MAXN];//length of word
int max_node;

void Init() {
  ver_node.push_back(0);//fake root
}

void TypeLetter(char L) {
  int curr=ver_node.back();
  if(trie[curr][L-'a']==0){
    max_node++;
    trie[curr][L-'a']=max_node;
    ver_node.push_back(max_node);
    let[max_node]=L;
    len[max_node]=len[curr]+1;
    up[0][max_node]=curr;
    for(int i=1;i<MAXL;i++){
      up[i][max_node]=up[i-1][up[i-1][max_node]];
    }
  }else{
    ver_node.push_back(trie[curr][L-'a']);
  }
}

void UndoCommands(int U) {
  int temp=ver_node[(ver_node.size()-1)-U];
  ver_node.push_back(temp);
}

char GetLetter(int P) {
  int curr=ver_node.back();
  int num=len[curr]-P-1;
  for(int i=0;i<MAXL;i++,num>>=1){
    if(num&1){
      curr=up[i][curr];
    }
  }
  return let[curr];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 1096 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 3 ms 1228 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 2 ms 844 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 124780 KB Output is correct
2 Correct 344 ms 137012 KB Output is correct
3 Correct 352 ms 133868 KB Output is correct
4 Correct 342 ms 102904 KB Output is correct
5 Correct 308 ms 116484 KB Output is correct
6 Correct 300 ms 147712 KB Output is correct
7 Correct 291 ms 73884 KB Output is correct
8 Correct 300 ms 110956 KB Output is correct
9 Correct 365 ms 151624 KB Output is correct
10 Correct 263 ms 111288 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 106936 KB Output is correct
2 Correct 414 ms 95132 KB Output is correct
3 Correct 349 ms 102584 KB Output is correct
4 Correct 365 ms 75452 KB Output is correct
5 Correct 301 ms 113044 KB Output is correct
6 Correct 290 ms 105400 KB Output is correct
7 Correct 290 ms 112832 KB Output is correct
8 Correct 384 ms 55724 KB Output is correct
9 Correct 411 ms 98668 KB Output is correct
10 Correct 264 ms 110552 KB Output is correct