oj.uz

Submission #84395

# Submission time Handle Problem Language Result Execution time Memory
84395 2018-11-15T04:11:53 Z updown1 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 762 ms 184616 KB 
/*
store what letter is 2^0 ahead, 2^1 ahead, ...
*/

char last;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=1000001;
///500,000,000
int N, pt[MAXN], len[MAXN], up[MAXN][20];
char let[MAXN];
bool num[MAXN];

void Init() {}
void TypeLetter(char L) {
    N++;
    let[N] = L;
    if (num[N-1]) up[N][0] = pt[N-1];
    else up[N][0] = N-1;
    len[N] = 1+len[up[N][0]];
    For (k, 1, 20) up[N][k] = up[up[N][k-1]][k-1];
}
void UndoCommands(int U) {
    N++;
    pt[N] = N-U-1;
    num[N] = true;
    if (num[pt[N]]) pt[N] = pt[pt[N]];
}
char GetLetter(int P) {
    int at = N;
    if (num[at]) at = pt[at];
    int x = len[at]-1-P;
    for (int k=19; k>=0; k--) if (x & (1<<k)) at = up[at][k];
    return let[at];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 516 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 892 KB Output is correct
8 Correct 2 ms 892 KB Output is correct
9 Correct 2 ms 892 KB Output is correct
10 Correct 2 ms 892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 984 KB Output is correct
4 Correct 2 ms 984 KB Output is correct
5 Correct 2 ms 988 KB Output is correct
6 Correct 2 ms 988 KB Output is correct
7 Correct 2 ms 996 KB Output is correct
8 Correct 2 ms 1000 KB Output is correct
9 Correct 2 ms 1008 KB Output is correct
10 Correct 2 ms 1008 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1140 KB Output is correct
2 Correct 4 ms 1324 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 3 ms 1640 KB Output is correct
7 Correct 3 ms 1660 KB Output is correct
8 Correct 3 ms 1684 KB Output is correct
9 Correct 4 ms 1712 KB Output is correct
10 Correct 4 ms 1792 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 67988 KB Output is correct
2 Correct 533 ms 85732 KB Output is correct
3 Correct 425 ms 90048 KB Output is correct
4 Correct 424 ms 99860 KB Output is correct
5 Correct 543 ms 99860 KB Output is correct
6 Correct 472 ms 112412 KB Output is correct
7 Correct 567 ms 112412 KB Output is correct
8 Correct 561 ms 120460 KB Output is correct
9 Correct 600 ms 121448 KB Output is correct
10 Correct 261 ms 135552 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 135552 KB Output is correct
2 Correct 725 ms 135552 KB Output is correct
3 Correct 388 ms 135552 KB Output is correct
4 Correct 409 ms 135552 KB Output is correct
5 Correct 495 ms 148564 KB Output is correct
6 Correct 445 ms 155932 KB Output is correct
7 Correct 454 ms 160292 KB Output is correct
8 Correct 627 ms 160292 KB Output is correct
9 Correct 762 ms 160292 KB Output is correct
10 Correct 266 ms 184616 KB Output is correct