oj.uz

Submission #256947

# Submission time Handle Problem Language Result Execution time Memory
256947 2020-08-03T12:33:07 Z blacktulip Klasika (COCI20_klasika) C++17
33 / 110
 350 ms 92536 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,say=1,nodee=1,visit[li*40][5],xorr[li];
int cev;
char s[10];
vector<int> v,vec;

inline void build_trie(){
	int node=1;
	for(int i=0;i<(int)v.size();i++){
		if(visit[node][v[i]])node=visit[node][v[i]];
		else{
			visit[node][v[i]]=++nodee;
			node=nodee;
		}
	}
}

inline void ask_trie(){
	int node=1;
	for(int i=0;i<(int)v.size();i++){
		if(visit[node][!v[i]]){node=visit[node][!v[i]];vec.pb(1);}
		else if(visit[node][v[i]]){node=visit[node][v[i]];vec.pb(0);}
		else break;
	}
}

main(void){
	//~ freopen("at.txt","r",stdin);
	//~ freopen("att.txt","w",stdout);
	scanf("%lld",&t);
	for(int i=1;i<=36;i++)v.pb(0);
	build_trie();
	while(t--){
		int x,y;
		scanf("%s %lld %lld",s,&x,&y);
		if(s[0]=='A'){
			xorr[++say]=(xorr[x]^y);
			int at=xorr[say];
			v.clear();
			while(at){
				v.pb(at%2);
				at/=2;
			}
			while((int)v.size()<35)v.pb(0);
			reverse(v.begin(),v.end());
			build_trie();
			continue;
		}
		int at=xorr[x];
		v.clear();
		while(at){
			v.pb(at%2);
			at/=2;
		}
		while((int)v.size()<35)v.pb(0);
		reverse(v.begin(),v.end());
		vec.clear();
		ask_trie();
		reverse(vec.begin(),vec.end());
		int ans=0;
		for(int i=0;i<(int)vec.size();i++){
			if(vec[i]==1)ans=(ans^(1ll<<i));
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Compilation message

klasika.cpp:53:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
klasika.cpp: In function 'int main()':
klasika.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&t);
  ~~~~~^~~~~~~~~~~
klasika.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %lld",s,&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 22.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 27080 KB Output is correct
2 Correct 346 ms 51832 KB Output is correct
3 Correct 350 ms 72184 KB Output is correct
4 Correct 341 ms 92280 KB Output is correct
5 Correct 275 ms 30000 KB Output is correct
6 Correct 302 ms 51960 KB Output is correct
7 Correct 312 ms 72312 KB Output is correct
8 Correct 332 ms 92412 KB Output is correct
9 Correct 271 ms 29816 KB Output is correct
10 Correct 302 ms 52220 KB Output is correct
11 Correct 302 ms 72568 KB Output is correct
12 Correct 305 ms 92536 KB Output is correct

Subtask #4
0 / 44.0

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