Submission #174674

#	Time	Username	Problem	Language	Result	Execution time	Memory
174674		mosiashvililuka	Xoractive (IZhO19_xoractive)	C++14	6 / 100	8 ms	1912 KiB

Xoractive

#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
int a,b,c,d,e,i,j,kl,n,l,r,ll,rr;
vector <int> pas,qw;
vector <pair <int, int> > qu[109];
multiset <int> s[109][109];
multiset <int> zx,xc,zzx;
pair <int, int> msh[109][109];
map <int, int> mp;
vector <int> mk(int q, int w){
	vector <int> mim;
	for(int h=q; h<=w; h++) mim.push_back(h);
	return mim;
}
multiset <int> geet(vector <int> q){
	q=get_pairwise_xor(q);
	multiset <int> mim;
	for(int h=0; h<q.size(); h++) mim.insert(q[h]);
	return mim;
}
void mkqu(int q, int w, int rr, pair <int, int> pp){
	if(w-q+1!=n-1){
		msh[q][w]=pp;
	}
	if(q==w) return;
	if(q!=(q+w)/2){if(kl<rr) kl=rr;qu[rr].push_back(make_pair(q,(q+w)/2));}
	mkqu(q,(q+w)/2,rr+1,make_pair(q,w));
	mkqu((q+w)/2+1,w,rr+1,make_pair(q,w));
}
vector <int> guess(int nzxc){
	n=nzxc;
	for(i=1; i<=n+1; i++) pas.push_back(0);
	if(n<=15){
		for(i=1; i<=n; i++){
			pas[i]=ask(i);
		}
		pas.erase(pas.begin());
		return pas;
	}
	pas[1]=ask(1);
	mkqu(2,n,1,make_pair(0,0));
	zx=geet(mk(1,n));
	xc=geet(mk(2,n));
	for(multiset <int>::iterator it=xc.begin(); it!=xc.end(); it++){
//		cout<<(*it)<<" fds "<<(*(zx.lower_bound((*it))))<<endl;
		zx.erase(zx.lower_bound((*it)));
	}
	mp.clear();
//	cout<<pas[1]<<endl;
	for(multiset <int>::iterator it=zx.begin(); it!=zx.end(); it++){
		if((*it)==0) continue;
		mp[(*it)]++;
		if(mp[(*it)]%2==1){
			s[2][n].insert(((*it)^pas[1]));
		}
	}
//	exit(0);
//cout<<kl<<endl;
	for(i=1; i<=kl; i++){
		qw.clear();
		for(j=0; j<qu[i].size(); j++){
			l=qu[i][j].first;r=qu[i][j].second;
	//		cout<<i<<" "<<l<<" "<<r<<endl;
			for(int h=l; h<=r; h++) qw.push_back(h);
		}
//		for(int h=0; h<qw.size(); h++) cout<<qw[h]<<" ";
//		cout<<endl;
		xc=geet(get_pairwise_xor(qw));
		qw.push_back(1);
		zx=geet(get_pairwise_xor(qw));
		zzx.clear();
		for(multiset <int>::iterator it=xc.begin(); it!=xc.end(); it++){
//		cout<<(*it)<<" fds "<<(*(zx.lower_bound((*it))))<<endl;
		zx.erase(zx.lower_bound((*it)));
	}
	mp.clear();
//	cout<<pas[1]<<" ds "<<endl;
	for(multiset <int>::iterator it=zx.begin(); it!=zx.end(); it++){
		if((*it)==0) continue;
		mp[(*it)]++;
		if(mp[(*it)]%2==1){
			zzx.insert(((*it)^pas[1]));
//			cout<<((*it)^pas[1])<<" l ";
		}
	}
	exit(0);
		for(j=0; j<qu[i].size(); j++){
			l=qu[i][j].first;r=qu[i][j].second;
			ll=msh[l][r].first;rr=msh[l][r].second;
			zx.clear();
			for(set <int>::iterator it=s[ll][rr].begin(); it!=s[ll][rr].end(); it++){
				multiset <int>::iterator t;
				t=zzx.lower_bound((*it));
				if(t==zzx.end()||(*t)!=(*it)){
					s[r+1][rr].insert((*it));
				}else{
					zx.insert((*it));
				}
			}
			s[l][r]=zx;
			if(l+1==r){
				pas[l]=ask(l);
//				cout<<zx.size()<<"   "<<l<<" "<<r<<" "<<ll<<" "<<rr<<endl;
			zx.erase(zx.lower_bound(pas[l]));
				pas[r]=(*zx.begin());
			}
		}
	}
	pas.erase(pas.begin());
	vector <int> nn;
	for(int h=1; h<=n; h++) nn.push_back(pas[h]);
	return nn;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::multiset<int> geet(std::vector<int>)':
Xoractive.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int h=0; h<q.size(); h++) mim.insert(q[h]);
               ~^~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<qu[i].size(); j++){
            ~^~~~~~~~~~~~~
Xoractive.cpp:88:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<qu[i].size(); j++){
            ~^~~~~~~~~~~~~

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