oj.uz

Submission #417158

# Submission time Handle Problem Language Result Execution time Memory
417158 2021-06-03T12:21:57 Z KalasLavas Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 552 ms 91184 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//#undef LOCALKL
#define IO \
ios_base::sync_with_stdio(0);(cin).tie(0);(cout).tie(0)
#define y1 y1_
#define prev prev_
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#ifdef LOCALKL
// #define cerr cerr<<"\33[1;32m"
// #define cout cout<<"\33[0m"
#else
#ifndef OO
#define endl '\n'
#define cerr if(1){}else cerr
#endif
#endif
#define OK cout<<"OK\n"<<endl;
#define setpre(k) fixed<<setprecision(k)
#define mmset(k,y) memset(k,y,sizeof(k))
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using pll = pair<long long,long long>;
using ull = unsigned long long;
using intt = long long;
using ll = long long;
using ld = long double;

const ll m9 = 998244353;
const ll m7 = 1000000007;
const ll m18 = 1000000000000000000;
const ll i127 = 2193062143;
const ll l127 = 9187201950435737471;

struct letter
{
	char x;
	int sz=0;
	int pos[21];
};

letter a[1000001];
int pos = 1;
void Init(){}

void TypeLetter(char L)
{
	a[pos].pos[0] = pos-1;
	for(int i=1;i<=20;i++)
		a[pos].pos[i] = a[a[pos].pos[i-1]].pos[i-1];
	a[pos].x = L;
	//cerr<<" > "<<pos<<' '<<L<<endl;
	a[pos].sz = a[pos-1].sz+1;
	pos++;
}

void UndoCommands(int U)
{
	a[pos] = a[pos-U-1];
	pos++;
}

char GetLetter(int P)
{
	int k = a[pos-1].sz-P-1;
	int poss = pos-1;
	//cerr<<" <> "<<poss<<' '<<k<<endl;
	while(k)
	{
		int i = 31-__builtin_clz(k);
		//cerr<<" >>> P "<<poss<<endl;
		k^=1<<i;
		poss=a[poss].pos[i];
	}
		//cerr<<" Print "<<poss<<endl;
	return a[poss].x;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 90180 KB Output is correct
2 Correct 36 ms 90252 KB Output is correct
3 Correct 36 ms 90208 KB Output is correct
4 Correct 35 ms 90240 KB Output is correct
5 Correct 39 ms 90276 KB Output is correct
6 Correct 42 ms 90180 KB Output is correct
7 Correct 36 ms 90232 KB Output is correct
8 Correct 36 ms 90296 KB Output is correct
9 Correct 35 ms 90284 KB Output is correct
10 Correct 35 ms 90284 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 90252 KB Output is correct
2 Correct 36 ms 90208 KB Output is correct
3 Correct 35 ms 90264 KB Output is correct
4 Correct 36 ms 90260 KB Output is correct
5 Correct 36 ms 90256 KB Output is correct
6 Correct 37 ms 90316 KB Output is correct
7 Correct 36 ms 90180 KB Output is correct
8 Correct 35 ms 90236 KB Output is correct
9 Correct 37 ms 90316 KB Output is correct
10 Correct 36 ms 90180 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 90320 KB Output is correct
2 Correct 36 ms 90308 KB Output is correct
3 Correct 38 ms 90364 KB Output is correct
4 Correct 37 ms 90268 KB Output is correct
5 Correct 37 ms 90268 KB Output is correct
6 Correct 37 ms 90268 KB Output is correct
7 Correct 38 ms 90324 KB Output is correct
8 Correct 36 ms 90192 KB Output is correct
9 Correct 38 ms 90296 KB Output is correct
10 Correct 40 ms 90200 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 90552 KB Output is correct
2 Correct 501 ms 90424 KB Output is correct
3 Correct 361 ms 90504 KB Output is correct
4 Correct 386 ms 90492 KB Output is correct
5 Correct 423 ms 90948 KB Output is correct
6 Correct 341 ms 90436 KB Output is correct
7 Correct 439 ms 90780 KB Output is correct
8 Correct 375 ms 90564 KB Output is correct
9 Correct 468 ms 90564 KB Output is correct
10 Correct 260 ms 90316 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 90740 KB Output is correct
2 Correct 552 ms 91144 KB Output is correct
3 Correct 352 ms 90692 KB Output is correct
4 Correct 384 ms 91184 KB Output is correct
5 Correct 360 ms 90692 KB Output is correct
6 Correct 403 ms 90564 KB Output is correct
7 Correct 386 ms 90568 KB Output is correct
8 Correct 537 ms 90936 KB Output is correct
9 Correct 550 ms 90928 KB Output is correct
10 Correct 261 ms 90380 KB Output is correct