Submission #288944

#	Time	Username	Problem	Language	Result	Execution time	Memory
288944		AMO5	Xoractive (IZhO19_xoractive)	C++17	6 / 100	7 ms	512 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"

using namespace std;

#define ii pair<int,int>
#define vi vector<int>
#define sz(x) (int)x.size()

vi ans;
set<int>p[111];
map<int,int>cnt[111];
int t[111];
/*
int ask(int i){
	return ans[i];
}

vi get_pairwise_xor(vi pos){
	vi ret;
	for(int x:pos){
		for(int y:pos){
			ret.emplace_back(ans[x]^ans[y]);
		}
	}
	sort(ret.begin(),ret.end());
	return ret;
}
*/ 

vi guess(int n){
	vi res;
	res.resize(n);
	if(n<=15){
		for(int i=0; i<n; i++)
			res[i]=ask(i+1);
		return res;
	}
	res[0]=(ask(1));
	int k=-1;
	while(n>=(1<<++k)){}
	cerr<<k<<"\n";
	for(int i=0; i<k; i++){
		vi q;
		for(int j=2; j<=n; j++){
			if(j>>i&1)q.emplace_back(j);
		}
		vi qq = q;
		vi qqq = get_pairwise_xor(q);
		qq.emplace_back(1);
		qq = get_pairwise_xor(qq);
		qq.erase(qq.begin());
		for(int x:qqq)
			qq.erase(find(qq.begin(),qq.end(),x));
		for(int ind:q){
			for(int x:qq){
				x=x^ans[0];
				t[ind]++;
				p[ind].insert(x);
				cnt[ind][x]++;
			}
		}
	}
	/*
	for(int i=2; i<=n; i++){
		cerr<<i<<" "<<sz(p[i])<<": ";
		for(int x:p[i])cerr<<"["<<x<<","<<cnt[i][x]<<"] ";
		cerr<<"\n";
	}
	// */ 
	priority_queue<ii,vector<ii>,greater<ii>>pq; //degree,ind
	for(int i=2; i<=n; i++){
		//cerr<<i<<" total: "<<t[i]<<"\n";
		pq.emplace(t[i],i);
	}
	while(!pq.empty()){
		int mx=0; vi val;
		int curind=0;
		vi hold;
		while(sz(pq)){
			ii now = pq.top();
			int deg = now.first;
			int ind = now.second;
			pq.pop();
			/*
			cerr<<deg<<" - "<<ind<<"\n";
			for(int x:p[ind])cerr<<x<<","<<cnt[ind][x]<<" ";
			cerr<<"\n";
			// */ 
			
			mx=-1;
			curind=ind;
			for(int x:p[ind]){
				if(cnt[ind][x]>mx){
					mx=cnt[ind][x];
					val = vi();
					val.emplace_back(x);
				}else if(cnt[ind][x]==mx){
					val.emplace_back(x);
				}
			}
			if(sz(val)==1)break;
			else hold.emplace_back(ind);
		}
		//cerr<<mx<<": ";
		mx = val[0];
		res[curind-1]=mx;
		//cerr<<curind<<" "<<mx<<" "<<cnt[curind][mx]<<"\n";
		for(int i=2; i<=n; i++){
			if(p[i].find(mx)!=p[i].end()){
				t[i]-=cnt[i][mx];
				p[i].erase(p[i].find(mx));
			}
		}
		for(int x:hold){
			pq.emplace(t[x],x);
		}
		/*
		for(int i=2; i<=n; i++){
			cerr<<i<<" total: "<<t[i]<<"\n";
		}
		// */ 
	}
	return res;
}
/*
int main(){
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	ans.emplace_back(0);
	for(int i=0; i<n; i++){
		int x; cin>>x;
		ans.emplace_back(x);
	}
	cerr<<"done input"<<"\n";
	vi ans2 = guess(n);
	for(int x:ans2)cout<<x<<" ";
	cout<<"\n";
	 
	return 0;
}
*/ 

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:82:8: warning: unused variable 'deg' [-Wunused-variable]
   82 |    int deg = now.first;
      |        ^~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 94