Submission #258884

#	Time	Username	Problem	Language	Result	Execution time	Memory
258884		errorgorn	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	564 ms	200548 KiB

scrivener

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());


int trie[1000005][26];
int par[1000005][22];
int d[1000005];
char letter[1000005];
int curr=0;
vector<int> pos;

int idx=1;

void Init() {
	memset(trie,-1,sizeof(trie));	
	memset(par,-1,sizeof(par));
	
	pos.push_back(curr);
}

void TypeLetter(char L) {
	int nxt=L-'a';
	if (trie[curr][nxt]==-1){
		trie[curr][nxt]=idx;
		d[idx]=d[curr]+1;
		
		int pp=par[idx][0]=curr;
		rep(x,0,22){
			if (par[pp][x]==-1) break;
			pp=par[idx][x+1]=par[pp][x];
		}
		
		letter[idx]=L;
		idx++;
	}
	curr=trie[curr][nxt];
	
	pos.push_back(curr);
}

void UndoCommands(int U) {
	curr=pos[sz(pos)-U-1];
	pos.push_back(curr);
}

char GetLetter(int p) {
	//for (auto &it:pos) cout<<it<<" "; cout<<endl;
	p=d[curr]-p-1;
	
	int pp=curr;
	rep(x,22,0) if (p&(1<<x)){
		pp=par[pp][x];
	}
	
	//cout<<curr<<" "<<pp<<endl;
	return letter[pp];
}

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