Submission #437131

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
437131	2021-06-25 22:05:03	aymane7	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	984 ms	130116 KiB

scrivener

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
vector<vector<int>> parent(N,vector<int>(21,0));
vector<char> letter(N);
vector<int> depth(N,0);
int cur=0;
void Init(){
    letter[0]='.';
}
void TypeLetter(char c){
    cur++;
    depth[cur]=depth[cur-1]+1;
    parent[cur][0]=cur-1;
    letter[cur]=c;
    for(int i=1;i<21;i++)
        parent[cur][i]=parent[parent[cur][i-1]][i-1];
}
void UndoCommands(int u){
    int nw=cur+1;
    depth[nw]=depth[cur-u];
    letter[nw]=letter[cur-u];
    for(int i=0;i<21;i++)
        parent[nw][i]=parent[cur-u][i];
    cur++;
}
char GetLetter(int pos){
    pos++;
    //find kth parent of cur st k=depth[cur]-pos
    int k=depth[cur]-pos;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40