oj.uz

답안 #370695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370695 2021-02-24T13:36:35 Z WLZ 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 930 ms 88056 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = (int) 1e6;
const int MAX_LOG = 20;
int sz = 0;
int up[MAXN][MAX_LOG + 1];
int len[MAXN];
char s[MAXN];

void Init() {}

void TypeLetter(char L) {
  s[sz] = L;
  len[sz] = 1;
  if (sz > 0) len[sz] += len[sz - 1];
  if (sz == 0) up[0][0] = 0;
  else up[sz][0] = sz - 1;
  for (int i = 1; i <= MAX_LOG; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
  sz++;
}

void UndoCommands(int U) {
  int idx = sz - U - 1;
  s[sz] = s[idx];
  len[sz] = len[idx];
  up[sz][0] = up[idx][0];
  for (int i = 1; i <= MAX_LOG; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
  sz++;
}

char GetLetter(int P) {
  P = len[sz - 1] - P - 1;
  int cur = sz - 1;
  for (int i = 0; i <= MAX_LOG; i++) if (P & (1 << i)) cur = up[cur][i];
  return s[cur];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 62700 KB Output is correct
2 Correct 553 ms 76652 KB Output is correct
3 Correct 444 ms 76396 KB Output is correct
4 Correct 557 ms 79980 KB Output is correct
5 Correct 479 ms 70764 KB Output is correct
6 Correct 397 ms 83308 KB Output is correct
7 Correct 918 ms 72632 KB Output is correct
8 Correct 869 ms 81516 KB Output is correct
9 Correct 506 ms 78612 KB Output is correct
10 Correct 347 ms 88056 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 57708 KB Output is correct
2 Correct 540 ms 49636 KB Output is correct
3 Correct 433 ms 63212 KB Output is correct
4 Correct 464 ms 54892 KB Output is correct
5 Correct 426 ms 73724 KB Output is correct
6 Correct 468 ms 76140 KB Output is correct
7 Correct 485 ms 76140 KB Output is correct
8 Correct 930 ms 64680 KB Output is correct
9 Correct 802 ms 63084 KB Output is correct
10 Correct 343 ms 87148 KB Output is correct