Submission #439881

#	Time	Username	Problem	Language	Result	Execution time	Memory
439881		AmShZ	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	811 ms	137324 KiB

scrivener

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 1e6 + 10;
const int xm = 20;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int n, a[xn], nxt[26][xn], par[xm][xn], v, m, H[xn];

void Init(){
}
void TypeLetter(char L){
	if (!nxt[L - 'a'][v])
		nxt[L - 'a'][v] = ++ n;
	int u = nxt[L - 'a'][v];
	par[0][u] = v;
	H[u] = H[v] + 1;
	v = u;
	for (int i = 1; i < xm; ++ i)
		par[i][v] = par[i - 1][par[i - 1][v]];
	a[++ m] = v;
}
void UndoCommands(int U){
	v = a[m - U], a[++ m] = v;
}
char GetLetter(int P){
	int d = H[v] - P, u = v;
	for (int i = xm - 1; i >= 0; -- i)
		if ((1 << i) < d)
			u = par[i][u], d -= (1 << i);
	for (int i = 0; i < 26; ++ i)
		if (u == nxt[i][par[0][u]])
			return char('a' + i);
}

/*
int main(){
	InTheNameOfGod;



	return 0;
}
*/

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40