oj.uz

Submission #231226

# Submission time Handle Problem Language Result Execution time Memory
231226 2020-05-13T05:41:36 Z cfalas Crayfish scrivener (IOI12_scrivener) C++14
74 / 100
 758 ms 262148 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;
   struct tri *children[27];
};

struct tri *getNode(){
    tri *n = new tri;
    for(int i=0;i<26;i++)
        n->children[i] = NULL;
    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 45 ms 82552 KB Output is correct
2 Correct 47 ms 82584 KB Output is correct
3 Correct 46 ms 82552 KB Output is correct
4 Correct 45 ms 82552 KB Output is correct
5 Correct 46 ms 82552 KB Output is correct
6 Correct 46 ms 82552 KB Output is correct
7 Correct 47 ms 82552 KB Output is correct
8 Correct 47 ms 82552 KB Output is correct
9 Correct 46 ms 82552 KB Output is correct
10 Correct 46 ms 82552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 82552 KB Output is correct
2 Correct 46 ms 82552 KB Output is correct
3 Correct 46 ms 82552 KB Output is correct
4 Correct 46 ms 82552 KB Output is correct
5 Correct 45 ms 82552 KB Output is correct
6 Correct 49 ms 82552 KB Output is correct
7 Correct 49 ms 82552 KB Output is correct
8 Correct 47 ms 82552 KB Output is correct
9 Correct 46 ms 82552 KB Output is correct
10 Correct 46 ms 82552 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 82936 KB Output is correct
2 Correct 49 ms 82940 KB Output is correct
3 Correct 47 ms 83064 KB Output is correct
4 Correct 47 ms 83320 KB Output is correct
5 Correct 55 ms 83036 KB Output is correct
6 Correct 48 ms 83448 KB Output is correct
7 Correct 47 ms 83448 KB Output is correct
8 Correct 47 ms 83320 KB Output is correct
9 Correct 48 ms 83380 KB Output is correct
10 Correct 48 ms 82936 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 236480 KB Output is correct
2 Correct 682 ms 253380 KB Output is correct
3 Correct 631 ms 250820 KB Output is correct
4 Correct 642 ms 220352 KB Output is correct
5 Correct 659 ms 229440 KB Output is correct
6 Runtime error 596 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 210392 KB Output is correct
2 Correct 728 ms 195928 KB Output is correct
3 Correct 575 ms 207288 KB Output is correct
4 Correct 565 ms 174784 KB Output is correct
5 Correct 576 ms 220224 KB Output is correct
6 Correct 577 ms 213032 KB Output is correct
7 Correct 595 ms 221244 KB Output is correct
8 Correct 698 ms 150092 KB Output is correct
9 Correct 758 ms 199368 KB Output is correct
10 Correct 437 ms 218816 KB Output is correct