oj.uz

Submission #138316

# Submission time Handle Problem Language Result Execution time Memory
138316 2019-07-29T18:11:31 Z dolphingarlic Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 972 ms 90872 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int dp[21][1000001], indx = 1, len_at[1000001];
char char_at[1000001];

void Init() {}

void TypeLetter(char L) { 
	char_at[indx] = L;
	len_at[indx] = len_at[indx - 1] + 1;

	dp[0][indx] = indx - 1;
	FOR(i, 1, 21) dp[i][indx] = dp[i - 1][dp[i - 1][indx]];
	
	indx++;
}

void UndoCommands(int U) {
	char_at[indx] = char_at[indx - U - 1];
	len_at[indx] = len_at[indx - U - 1];

	dp[0][indx] = dp[0][indx - U - 1];
	FOR(i, 1, 21) dp[i][indx] = dp[i - 1][dp[i - 1][indx]];

	indx++;
}

char GetLetter(int P) {
	int curr = indx - 1, x = len_at[indx - 1] - P - 1;
	for (int i = 0; x > 0; i++) {
		if (x & 1) curr = dp[i][curr];
		x >>= 1;
	}

	return char_at[curr];
}

// int main() {
// 	ios_base::sync_with_stdio(0), cin.tie(0);

//     int t;
//     cin >> t;
//     Init();
//     for (int i = 0; i < t; i++) {
//         char c, d;
//         int e;
//         cin >> c;
//         switch (c) {
//             case 'T':
//                 cin >> d;
//                 TypeLetter(d);
//                 break;
//             case 'P':
//                 cin >> e;
//                 cout << GetLetter(e) << '\n';
//                 break;
//             default:
//                 cin >> e;
//                 UndoCommands(e);
//         }
//     }
// }

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 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 516 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 66692 KB Output is correct
2 Correct 439 ms 80632 KB Output is correct
3 Correct 482 ms 80760 KB Output is correct
4 Correct 426 ms 85880 KB Output is correct
5 Correct 359 ms 75112 KB Output is correct
6 Correct 312 ms 87148 KB Output is correct
7 Correct 972 ms 76964 KB Output is correct
8 Correct 728 ms 85368 KB Output is correct
9 Correct 398 ms 81528 KB Output is correct
10 Correct 312 ms 90872 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 62072 KB Output is correct
2 Correct 457 ms 55176 KB Output is correct
3 Correct 430 ms 68828 KB Output is correct
4 Correct 413 ms 61584 KB Output is correct
5 Correct 346 ms 78320 KB Output is correct
6 Correct 353 ms 80820 KB Output is correct
7 Correct 323 ms 80760 KB Output is correct
8 Correct 848 ms 70016 KB Output is correct
9 Correct 680 ms 67208 KB Output is correct
10 Correct 303 ms 89844 KB Output is correct