oj.uz

Submission #130258

# Submission time Handle Problem Language Result Execution time Memory
130258 2019-07-14T12:02:37 Z khulegub Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 1000 ms 139156 KB 
#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;


/*

#############################################
# x X x _ P u $ $ y S l a y e r 6 9 _ x X x #
#############################################

*/

/*
Check array size
Check IO
*/

int curr;
vector<pair<char, int> > s; //storing chars and ranks
// vector<int> node_par; //storing each node's origin
int node_par[1000005][22]; //nodes parents
int par[1000005][22]; //cmds parents
// vector<int> node_par[22];
// // vector<int> par; //storing each cmd's origin
// vector<int> par[22]; //bin uplifting
vector<int> pos; //storing each cmd's position in "s"
void Init() {
	s.pb(mp('#', 0));
	curr = 0; //current cmd is 0
	pos.pb(0); //cmd 0 s position of node is 0
	node_par[0][0] = 0;
	par[0][0] = 0;
	// node_par.pb(0);
	// par.pb(0); //cmd zero came from zero lol
}
void TypeLetter(char L) {
	par[curr + 1][0] = curr; //2 ^ 0 th parent
	for (int i = 1; i <= 22; i++){
		par[curr + 1][i] = par[ par[curr + 1][i - 1] ][i - 1];
		if (par[curr + 1][i] == 0 ) break;
	}

	s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node
	int node_curr = s.size() - 1;
	node_par[node_curr][0] = pos[curr];
	for (int i = 1; i <= 22; i++){
		node_par[node_curr][i] = node_par[ node_par[node_curr][i - 1] ][i - 1];
		if (node_par[node_curr][i] == 0 ) break;
	}
	pos.pb(s.size() - 1);
	curr++;
}
void UndoCommands(int U) {
	int origin = curr;
	// need to uplift U times
	for (int i = 0; i <= 22; i++){ // decompose U into binary
		if ( (U & (1 << i)) ){
			origin = par[origin][i];
		}
	}
	par[curr + 1][0] = curr; //2 ^ 0 th parent
	for (int i = 1; i <= 22; i++){
		par[curr + 1][i] = par[ par[curr + 1][i - 1] ][i - 1];
		if (par[curr + 1][i] == 0 ) break;
	}
	curr++;
	pos.pb(pos[origin]);
}
char GetLetter(int P) {
	P++;
	int tmp = pos[curr];
	int j = s[tmp].yy - P;
	for (int i = 0; i <= 22; i++ ){
		if ( (j & (1 << i))){
			tmp = node_par[tmp][i];
		}
	}
	return s[tmp].xx;
}


// int main(){ //driver-chan
// 	Init();
// 	TypeLetter('a');
// 	cout << GetLetter(0);
// 	TypeLetter('b');
// 	cout << GetLetter(0);
// 	cout << GetLetter(1);
// 	UndoCommands(1);
// 	cout << GetLetter(0);
// 	TypeLetter('c');
// 	cout << GetLetter(1);
// 	// for (auto c : s){
// 	// 	cout << c.yy ;
// 	// }
// 	// cout << s.xx;
// }



/*
Atsaa hiiged bgan??
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 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 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 4 ms 1016 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 119356 KB Output is correct
2 Execution timed out 1051 ms 139156 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 105420 KB Output is correct
2 Correct 919 ms 91420 KB Output is correct
3 Correct 816 ms 109588 KB Output is correct
4 Correct 864 ms 88532 KB Output is correct
5 Correct 797 ms 124600 KB Output is correct
6 Correct 854 ms 124208 KB Output is correct
7 Correct 819 ms 127436 KB Output is correct
8 Execution timed out 1082 ms 84860 KB Time limit exceeded
9 Halted 0 ms 0 KB -