Submission #130262

#	Time	Username	Problem	Language	Result	Execution time	Memory
130262		khulegub	Crayfish scrivener (IOI12_scrivener)	C++14	5 / 100	82 ms	20232 KiB

scrivener

#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;

/*
IM RETARDED, JUST SO YOU KNOW LOL.
*/

/*
 
#############################################
# 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[100005][20]; //nodes parents
int par[100005]; //cmds parents
// vector<int> node_par[20];
// vector<int> par; //storing each cmd's origin
// vector<int> par[20]; //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;
	// node_par.pb(0);
	// par.pb(0); //cmd zero came from zero lol
}
void TypeLetter(char L) {
	par[curr + 1] = curr; 
	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 <= 20; i++){
		node_par[node_curr][i] = node_par[ node_par[node_curr][i - 1] ][i - 1];
	}
	pos.pb(s.size() - 1);
	curr++;
}
void UndoCommands(int U) {
	int origin = par[curr - U];
	par[curr + 1] = curr; //2 ^ 0 th parent
	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 <= 20; i++ ){
		if ( (j & (1 << i))){
			tmp = node_par[tmp][i];
		}
	}
	return s[tmp].xx;
}

Compilation message (stderr)

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:49:26: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   node_par[node_curr][i] = node_par[ node_par[node_curr][i - 1] ][i - 1];
   ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scrivener.cpp:48:20: note: within this loop
  for (int i = 1; i <= 20; i++){
                  ~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40