Submission #99773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99773	2019-03-07T03:33:46 Z	PeppaPig	Crayfish scrivener (IOI12_scrivener)	C++14	60 / 100	1000 ms	144760 KB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;

struct node {
    char d;
    int sz;
    node *par[21];
    node() { }
    node(char d) : d(d) { for(int i = 0; i <= 20; i++) par[i] = NULL; }
};

int ptr;
node* S[N];

void Init() {
    ptr = 0;
    S[0] = NULL; 
}

void TypeLetter(char L) {
    ++ptr;
    S[ptr] = new node(L);
    S[ptr]->sz = S[ptr-1] ? S[ptr-1]->sz + 1 : 1;
    S[ptr]->par[0] = S[ptr-1];
    for(int i = 1; i <= 20; i++) if(S[ptr]->par[i-1])
        S[ptr]->par[i] = S[ptr]->par[i-1]->par[i-1];
}

void UndoCommands(int U) {
    S[++ptr] = S[ptr - U];
}

char GetLetter(int P) {
    int d = S[ptr]->sz - P - 1;
    node* now = S[ptr];
    for(int i = 20; ~i; i--) if(d >> i & 1) now = now->par[i];
    return now->d;
}

Compilation message

scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:33:7: warning: operation on 'ptr' may be undefined [-Wsequence-point]
     S[++ptr] = S[ptr - U];
       ^~~~~

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

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

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	870 ms	118724 KB	Output is correct
2	Correct	897 ms	131144 KB	Output is correct
3	Correct	631 ms	129340 KB	Output is correct
4	Correct	550 ms	104952 KB	Output is correct
5	Correct	682 ms	112748 KB	Output is correct
6	Correct	736 ms	141944 KB	Output is correct
7	Correct	666 ms	71892 KB	Output is correct
8	Correct	833 ms	106344 KB	Output is correct
9	Correct	976 ms	144760 KB	Output is correct
10	Correct	317 ms	106700 KB	Output is correct

Subtask #5

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	952 ms	102220 KB	Output is correct
2	Execution timed out	1049 ms	90876 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-