Submission #99775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99775	2019-03-07T03:40:31 Z	PeppaPig	Crayfish scrivener (IOI12_scrivener)	C++14	60 / 100	1000 ms	140408 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	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	356 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	3 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	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	3 ms	640 KB	Output is correct
2	Correct	4 ms	640 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	4 ms	896 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	4 ms	1024 KB	Output is correct
7	Correct	4 ms	1152 KB	Output is correct
8	Correct	4 ms	896 KB	Output is correct
9	Correct	4 ms	896 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	866 ms	115036 KB	Output is correct
2	Correct	910 ms	126968 KB	Output is correct
3	Correct	557 ms	124388 KB	Output is correct
4	Correct	510 ms	98680 KB	Output is correct
5	Correct	658 ms	108152 KB	Output is correct
6	Correct	769 ms	137848 KB	Output is correct
7	Correct	701 ms	65896 KB	Output is correct
8	Correct	773 ms	100932 KB	Output is correct
9	Correct	885 ms	140408 KB	Output is correct
10	Correct	270 ms	102648 KB	Output is correct

Subtask #5

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	920 ms	97820 KB	Output is correct
2	Correct	942 ms	85628 KB	Output is correct
3	Correct	500 ms	94696 KB	Output is correct
4	Correct	425 ms	69744 KB	Output is correct
5	Correct	686 ms	104312 KB	Output is correct
6	Correct	615 ms	98100 KB	Output is correct
7	Correct	655 ms	104616 KB	Output is correct
8	Correct	760 ms	48672 KB	Output is correct
9	Execution timed out	1081 ms	87840 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-