oj.uz

Submission #231230

# Submission time Handle Problem Language Result Execution time Memory
231230 2020-05-13T05:47:07 Z cfalas Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 765 ms 192452 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 82556 KB Output is correct
2 Correct 56 ms 82552 KB Output is correct
3 Correct 54 ms 82552 KB Output is correct
4 Correct 55 ms 82688 KB Output is correct
5 Correct 55 ms 82552 KB Output is correct
6 Correct 54 ms 82552 KB Output is correct
7 Correct 55 ms 82552 KB Output is correct
8 Correct 54 ms 82552 KB Output is correct
9 Correct 54 ms 82552 KB Output is correct
10 Correct 55 ms 82552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 82560 KB Output is correct
2 Correct 56 ms 82552 KB Output is correct
3 Correct 54 ms 82556 KB Output is correct
4 Correct 53 ms 82552 KB Output is correct
5 Correct 54 ms 82552 KB Output is correct
6 Correct 53 ms 82552 KB Output is correct
7 Correct 54 ms 82552 KB Output is correct
8 Correct 55 ms 82552 KB Output is correct
9 Correct 54 ms 82552 KB Output is correct
10 Correct 53 ms 82552 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 82680 KB Output is correct
2 Correct 56 ms 82808 KB Output is correct
3 Correct 56 ms 82808 KB Output is correct
4 Correct 59 ms 83064 KB Output is correct
5 Correct 55 ms 82808 KB Output is correct
6 Correct 57 ms 83064 KB Output is correct
7 Correct 56 ms 83116 KB Output is correct
8 Correct 57 ms 82992 KB Output is correct
9 Correct 56 ms 83064 KB Output is correct
10 Correct 54 ms 82808 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 168896 KB Output is correct
2 Correct 673 ms 179140 KB Output is correct
3 Correct 633 ms 177212 KB Output is correct
4 Correct 671 ms 159684 KB Output is correct
5 Correct 646 ms 165180 KB Output is correct
6 Correct 656 ms 191292 KB Output is correct
7 Correct 615 ms 143804 KB Output is correct
8 Correct 637 ms 168128 KB Output is correct
9 Correct 723 ms 192452 KB Output is correct
10 Correct 467 ms 169024 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 156712 KB Output is correct
2 Correct 718 ms 152024 KB Output is correct
3 Correct 614 ms 155196 KB Output is correct
4 Correct 587 ms 137680 KB Output is correct
5 Correct 573 ms 163516 KB Output is correct
6 Correct 553 ms 159548 KB Output is correct
7 Correct 608 ms 164028 KB Output is correct
8 Correct 701 ms 125472 KB Output is correct
9 Correct 765 ms 151360 KB Output is correct
10 Correct 453 ms 164156 KB Output is correct