oj.uz

답안 #43802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43802 2018-03-24T03:13:18 Z PowerOfNinjaGo 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 652 ms 150388 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e6+5;
int dp[25][maxn];
char txt[maxn];
int sz[maxn];
int ver[maxn];
int rounds = 1;
int n = 1;
void Init()
{
    return;
}

int kth(int u, int k)
{
    for(int i = 22; i>= 0; i--)
    {
        if((1<<i)<= k)
        {
            u = dp[i][u];
            k -= 1<<i;
        }
    }
    return u;
}
void TypeLetter(char L)
{
    int lver = ver[rounds-1];
    dp[0][n] = lver;
    for(int i = 1; i<= 22; i++) dp[i][n] = dp[i-1][dp[i-1][n]];
    sz[n] = 1+sz[lver];
    //printf("sz[%d] = %d\n", n, sz[n]);
    //printf("ver[%d] = %d\n", rounds, n);
    txt[n] = L;
    ver[rounds] = n;
    rounds++; n++;
}

void UndoCommands(int U)
{
    int want = ver[rounds-U-1];
    ver[rounds] = want;
    rounds++;
}

char GetLetter(int P)
{
    P = sz[ver[rounds-1]]-P-1;
    //printf("P is %d\n", P);
    int tmp = kth(ver[rounds-1], P);
    return txt[tmp];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 756 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 1 ms 780 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 784 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 2 ms 792 KB Output is correct
4 Correct 2 ms 796 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 1 ms 804 KB Output is correct
7 Correct 2 ms 808 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 944 KB Output is correct
10 Correct 1 ms 944 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1036 KB Output is correct
2 Correct 4 ms 1176 KB Output is correct
3 Correct 3 ms 1216 KB Output is correct
4 Correct 3 ms 1388 KB Output is correct
5 Correct 4 ms 1388 KB Output is correct
6 Correct 3 ms 1460 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 4 ms 1528 KB Output is correct
9 Correct 3 ms 1532 KB Output is correct
10 Correct 3 ms 1532 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 62924 KB Output is correct
2 Correct 419 ms 73036 KB Output is correct
3 Correct 389 ms 76632 KB Output is correct
4 Correct 391 ms 76632 KB Output is correct
5 Correct 380 ms 79252 KB Output is correct
6 Correct 301 ms 98316 KB Output is correct
7 Correct 409 ms 98316 KB Output is correct
8 Correct 327 ms 98316 KB Output is correct
9 Correct 482 ms 115164 KB Output is correct
10 Correct 255 ms 115164 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 505 ms 115164 KB Output is correct
2 Correct 652 ms 115164 KB Output is correct
3 Correct 392 ms 115164 KB Output is correct
4 Correct 384 ms 115164 KB Output is correct
5 Correct 309 ms 127184 KB Output is correct
6 Correct 344 ms 128520 KB Output is correct
7 Correct 325 ms 136436 KB Output is correct
8 Correct 525 ms 136436 KB Output is correct
9 Correct 576 ms 139768 KB Output is correct
10 Correct 236 ms 150388 KB Output is correct