oj.uz

Submission #23616

# Submission time Handle Problem Language Result Execution time Memory
23616 2017-05-16T12:17:06 Z mohammad_kilani Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 783 ms 142472 KB 
//#include"grader.h"
#include<vector>
using namespace std;

int node = 0;
int lastnode = 0;
vector<pair<int,char> > g[1000010];
int dp[23][1000010];
vector<int> curnode;
char chr[1000100];
int depth[1000100];

void Init() {
    dp[0][0] = -1;
    curnode.push_back(0);
    return;
}

void TypeLetter(char L) {
    node++;
    g[lastnode].push_back(make_pair(node,L));
    dp[0][node] = lastnode;
    for(int k=1;k<=22;k++){
        if(dp[k-1][node] == -1)
            dp[k][node] = -1;
        else
            dp[k][node] = dp[k-1][dp[k-1][node]];
    }
    chr[node] = L;
    depth[node] = depth[lastnode] + 1;
    curnode.push_back(node);
    lastnode = node;
}

void UndoCommands(int U) {
    int tmpnode = curnode[curnode.size()-U-1];
    lastnode = tmpnode;
    curnode.push_back(lastnode);
}

char GetLetter(int P) {
    int u = lastnode;
    P++;
    for(int i=22;i>=0;i--){
        if(depth[u]-(1<<i) >= P){
            u = dp[i][u];
        }
    }
    return chr[u];

}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 119476 KB Output is correct
2 Correct 9 ms 119476 KB Output is correct
3 Correct 6 ms 119476 KB Output is correct
4 Correct 6 ms 119608 KB Output is correct
5 Correct 9 ms 119476 KB Output is correct
6 Correct 3 ms 119608 KB Output is correct
7 Correct 9 ms 119616 KB Output is correct
8 Correct 9 ms 119636 KB Output is correct
9 Correct 3 ms 119608 KB Output is correct
10 Correct 16 ms 119612 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 139172 KB Output is correct
2 Correct 513 ms 140096 KB Output is correct
3 Correct 486 ms 139436 KB Output is correct
4 Correct 479 ms 134688 KB Output is correct
5 Correct 513 ms 132580 KB Output is correct
6 Correct 383 ms 137180 KB Output is correct
7 Correct 463 ms 133364 KB Output is correct
8 Correct 419 ms 139040 KB Output is correct
9 Correct 513 ms 142472 KB Output is correct
10 Correct 279 ms 129272 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 136268 KB Output is correct
2 Correct 783 ms 136076 KB Output is correct
3 Correct 473 ms 135080 KB Output is correct
4 Correct 499 ms 132644 KB Output is correct
5 Correct 433 ms 135608 KB Output is correct
6 Correct 383 ms 131912 KB Output is correct
7 Correct 419 ms 133240 KB Output is correct
8 Correct 563 ms 130664 KB Output is correct
9 Correct 616 ms 137192 KB Output is correct
10 Correct 283 ms 129140 KB Output is correct