Submission #231230

#	Time	Username	Problem	Language	Result	Execution time	Memory
231230		cfalas	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	765 ms	192452 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef map<ll,ll> mii;

#define L 20
#define INF 1000001

int d[INF];
struct tri{
	char lastlet;
	map<int, tri*> children;
   //struct tri *children[27];
};

struct tri *getNode(){
    tri *n = new tri;
    return n;

}

int upp[INF][L+1] = {};
int anc(int n, int k){
	int cnt=0;
	if(k>d[n]) return 0;
	while(k>0){
		if(k%2) n = upp[n][cnt];
		cnt++;
		k/=2;
	}
	return n;
}

void pre(int n){
	//cout<<n<<endl;
	for(int i=1;i<L;i++){
		upp[n][i] = anc(upp[n][0], (1ll<<i)-1);
		//cout<<i<<" "<<upp[n][i]<<endl;
	}
	//cout<<"---\n";
}

tri *trie;

void pr(int ind=0, tri* z=trie, tri* node=NULL){
	for(int i=0;i<26;i++){
		if(z->children[i]!=NULL){
			cout<<"\\";
			for(int i=0;i<ind;i++) cout<<' ';
			if(z->children[i]!=node) cout<<(char)(i+'a')<<endl;
			else cout<<(char)(i+'A')<<endl;
			pr(ind+1, z->children[i], node);
		}
	}
}

vector<pair<tri*, int> > history;
void Init(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	trie = getNode();
	for(int i=0;i<INF;i++){
		for(int j=0;j<=L;j++){
			upp[i][j] = INF+10;
		}
	}
	history.push_back(make_pair(trie, 0));

}

void TypeLetter(char a){
	history[history.size()-1].F->children[a-'a'] = getNode();
	upp[history.size()][0] = history[history.size()-1].S;
	//cout<<"| "<<history.size()<<endl;
	d[history.size()] = d[history[history.size()-1].S]+1;
	history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
	history[history.size()-1].F->lastlet = a;
	//pr(0, trie, history[history.size()-1].F);
	pre(history[history.size()-1].S);
}

void UndoCommands(int a){
	d[history.size()] = d[history[history.size()-1-a].S];
	history.push_back(history[history.size()-a-1]);
}

char GetLetter(int pos){
	return history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet;
}

/*
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	trie = getNode();
    int n;
    cin>>n;
	for(int i=0;i<INF;i++){
		for(int j=0;j<=L;j++){
			upp[i][j] = INF+10;
		}
	}
	vector<pair<tri*, int> > history;
	history.push_back(make_pair(trie, 0));
    while(n--){
        char c;
        cin>>c;
		//cout<<c<<" ";
        if(c=='T'){
            char a;
            cin>>a;
            //trie[TIME]->children[a-'a'] = getNode();
			history[history.size()-1].F->children[a-'a'] = getNode();
			upp[history.size()][0] = history[history.size()-1].S;
			//cout<<"| "<<history.size()<<endl;
			d[history.size()] = d[history[history.size()-1].S]+1;
			history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
			history[history.size()-1].F->lastlet = a;
			//pr(0, trie, history[history.size()-1].F);
			pre(history[history.size()-1].S);
			//cout<<"---------\n";
        }
        if(c=='U'){
            int a;
            cin>>a;
			//cout<<" "<<history.size()<<endl;
			d[history.size()] = d[history[history.size()-1-a].S];
			history.push_back(history[history.size()-a-1]);
			//pr(0, trie, history[history.size()-1].F);
			//cout<<"---------\n";
        }
        if(c=='P'){
            int pos;
            cin>>pos;
			/
			string s = "";
			int q = history[history.size()-1].S;
			while(q!=0){
				s+=history[q].F->lastlet;
				q = upp[q][0];
			}
			cout<<s[s.size()-pos-1]<<endl;
			/
			//pre(history[history.size()-1].S);
			cout<<history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet<<"\n";
        }
    }
	//pr();
}
*/

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