oj.uz

Submission #260608

# Submission time Handle Problem Language Result Execution time Memory
260608 2020-08-10T15:12:59 Z ElyesChaabouni Crayfish scrivener (IOI12_scrivener) C++14
5 / 100
 758 ms 102632 KB 
/*#pragma GCC optimize("O3")*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
//#define ordered_set tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
using namespace std;
int pos=0, cur=0;
int v[1000005], depth[1000005];
vector<char>tree;
vector<int> anc[1000005];
void process(int x, int y)
{
	int nb=0;
	bool ok=true;
	anc[x].push_back(y);
	while(ok)
	{
		int cu=anc[x].back();
		if(anc[cu].size() > nb)
		{
			anc[x].push_back(anc[cu][nb]);
			nb++;
		}
		else
			ok=false;
	}
}
char find_kth(int x, int k)
{
	int nb=0;
	while(k)
	{
		if(k%2==1)
			x=anc[x][nb];
		nb++;
		k/=2;
	}
	return tree[x];
}
void Init()
{
	tree.clear();
	tree.push_back('0');
	depth[0]=0;
	v[0]=0;
	cur=0;
	for(int i = 0; i < 1000005; i++)
	{
		anc[i].clear();
	}
	pos=0;
}
void TypeLetter(char L)
{
	cur++;
	tree.push_back(L);
	process(tree.size()-1, pos);
	depth[cur]=(depth[pos]+1);
	pos=tree.size()-1;
	v[cur]=(pos);
	//cout << pos << ' ' << tree[pos] << '\n';
}
void UndoCommands(int U)
{
	cur++;
	pos=v[cur-1-U];
	v[cur]=pos;
	depth[cur]=(depth[cur-1-U]);
	//cout << pos << ' ' << tree[pos] << '\n';
}
char GetLetter(int P)
{
	P++;
	return find_kth(pos, depth[cur]-P);
}
/*int main()
{
	while(1)
	{
		int t;
		cin >> t;
		if(t==0)
			Init();
		if(t==1)
		{
			char c;
			cin >> c;
			TypeLetter(c);
		}
		if(t==2)
		{
			int x;
			cin >> x;
			UndoCommands(x);
		}
		if(t==3)
		{
			int x;
			cin >> x;
			cout << GetLetter(x) << '\n';
		}
	}
}*/
//size

Compilation message

scrivener.cpp: In function 'void process(int, int)':
scrivener.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(anc[cu].size() > nb)
      ~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23840 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 18 ms 23872 KB Output is correct
6 Correct 18 ms 23840 KB Output is correct
7 Correct 19 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Incorrect 17 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 755 ms 102632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 758 ms 89200 KB Output isn't correct
2 Halted 0 ms 0 KB -