oj.uz

Submission #226228

# Submission time Handle Problem Language Result Execution time Memory
226228 2020-04-23T05:41:50 Z thtsshz_bgwrswh Crayfish scrivener (IOI12_scrivener) C++17
34 / 100
 714 ms 262148 KB 
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<random>
#include<time.h>
#include<algorithm>
using namespace std;
struct Treap{
	Treap *l,*r;
	int sz;
	char c;
	Treap(){}
	Treap(char _c){
		c=_c;
		sz=1;
		l=r=0;
	}
}*treap[1000025];
int cnt;
void pull(Treap *t){
	t->sz=(t->l?t->l->sz:0)+(t->r?t->r->sz:0)+1;
}  
void copy(Treap *&a,Treap *&b){
	a=new Treap;
	a->l=b->l;
	a->r=b->r;
	a->sz=b->sz;
	a->c=b->c;
}
Treap* merge(Treap *a,Treap *b){
	if(!a||!b)
		return a?a:b;
	Treap *t;
	if(rand()%(a->sz+b->sz)<a->sz){
		copy(t,a);
		t->r=merge(a->r,b);
		pull(t);
	}
	else{
		copy(t,b);
		t->l=merge(a,b->l);
		pull(t);
	}
	return t;
}
void split(Treap *t,Treap *&a,Treap *&b,int k){
	if(!t){
		a=b=0;
		return;
	}
	int l_sz=t->l?t->l->sz:0;
	if(l_sz+1<=k){
		copy(a,t);
		split(t->r,a->r,b,k-l_sz-1);
		pull(a);
	}
	else{
		copy(b,t);
		split(t->l,a,b->l,k);
		pull(b);
	}
}
void Init(){
	fill(treap,treap+1000025,nullptr);
	cnt=0;
}
void TypeLetter(char c){
	cnt++;
	treap[cnt]=merge(treap[cnt-1],new Treap(c));
}
void UndoCommands(int k){
	cnt++;
	treap[cnt]=treap[cnt-k-1];
}
char GetLetter(int k){
	Treap *left=0,*right=0;
	split(treap[cnt],left,treap[cnt],k);
	split(treap[cnt],treap[cnt],right,1);
	char temp=treap[cnt]->c;
	treap[cnt]=merge(merge(left,treap[cnt]),right);
	return temp;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 8 ms 8192 KB Output is correct
4 Correct 8 ms 8192 KB Output is correct
5 Correct 9 ms 8320 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 8 ms 8192 KB Output is correct
9 Correct 8 ms 8192 KB Output is correct
10 Correct 8 ms 8192 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8064 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8168 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 10 ms 8192 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 10 ms 8192 KB Output is correct
9 Correct 8 ms 8192 KB Output is correct
10 Correct 8 ms 8192 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8704 KB Output is correct
2 Correct 13 ms 10240 KB Output is correct
3 Correct 11 ms 9216 KB Output is correct
4 Correct 12 ms 8960 KB Output is correct
5 Correct 11 ms 9344 KB Output is correct
6 Correct 12 ms 9344 KB Output is correct
7 Correct 12 ms 9472 KB Output is correct
8 Correct 11 ms 9216 KB Output is correct
9 Correct 11 ms 9600 KB Output is correct
10 Correct 10 ms 8704 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 558 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 714 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -