oj.uz

Submission #553357

# Submission time Handle Problem Language Result Execution time Memory
553357 2022-04-25T14:49:42 Z pokmui9909 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 564 ms 139856 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll Q;
ll P[1000005][22];
char C[1000005];
ll D[1000005];
ll n = 0, m = 0;
vector<ll> V;
void Init(){}
void TypeLetter(char c){
  	m++;
    C[m] = c;
    V.push_back(m);
    D[m] = D[n] + 1;
    P[m][0] = n;
    for(ll j = 1; j < 22; j++){
        P[m][j] = P[P[m][j - 1]][j - 1];
    }
    n = m;
}
void UndoCommands(int k){
    n = V[V.size() - 1 - k];
    V.push_back(n);
}
char GetLetter(int k){
    k = D[n] - k - 1;
    ll u = n;
    for(ll j = 0; j < 22; j++){
        if(k & (1 << j)){
            u = P[u][j];
        }
    }
    return C[u];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 968 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 2 ms 708 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 114572 KB Output is correct
2 Correct 504 ms 126736 KB Output is correct
3 Correct 375 ms 124892 KB Output is correct
4 Correct 342 ms 101508 KB Output is correct
5 Correct 442 ms 108972 KB Output is correct
6 Correct 438 ms 137148 KB Output is correct
7 Correct 462 ms 69568 KB Output is correct
8 Correct 442 ms 102732 KB Output is correct
9 Correct 564 ms 139856 KB Output is correct
10 Correct 257 ms 103312 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 98756 KB Output is correct
2 Correct 512 ms 87936 KB Output is correct
3 Correct 371 ms 96748 KB Output is correct
4 Correct 373 ms 74012 KB Output is correct
5 Correct 386 ms 105168 KB Output is correct
6 Correct 421 ms 99304 KB Output is correct
7 Correct 398 ms 105492 KB Output is correct
8 Correct 462 ms 52916 KB Output is correct
9 Correct 559 ms 91024 KB Output is correct
10 Correct 262 ms 102344 KB Output is correct