Submission #311293

#	Time	Username	Problem	Language	Result	Execution time	Memory
311293		mosiashvililuka	Xoractive (IZhO19_xoractive)	C++17	6 / 100	13 ms	1536 KiB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[109],l,r,mid,cnt,n,A[109];
map <int, int> fx;
deque <pair <int, int> > de;
multiset <int> s,ss;
multiset <int>::iterator it,t;
vector <int> v[109][109],vv,z;
multiset <int> askk(vector <int> q){
	multiset <int> qw;
	vector <int> w=get_pairwise_xor(q);
	for(i=0; i<w.size(); i++){
		qw.insert(w[i]);
	}
	return qw;
}
void dele(){
	for(it=s.begin(); it!=s.end(); it++) ss.erase(ss.lower_bound((*it)));
	while(ss.size()>0&&(*ss.begin())==0) ss.erase(ss.begin());
}
vector<int> guess(int nn) {
	n=nn;
	a=n;
	vector <int> ans;
	if(n<=4){
		for(i=1; i<=n; i++) f[i]=ask(i);
		for(i=1; i<=n; i++){
			ans.push_back(f[i]);
		}
		return ans;
	}
	de.push_back(make_pair(2,a));
	for(i=2; i<=a; i++){
		vv.push_back(i);
	}
	f[1]=ask(1);
	s=askk(vv);
	vv.push_back(1);
	ss=askk(vv);
	dele();
	for(it=ss.begin(); it!=ss.end(); it++){
		v[2][a].push_back(((*it)^f[1]));
	}
	while(de.size()){
		e=de.size();
		vv.clear();
		for(ii=0; ii<e; ii++){
			if(de[ii].second==de[ii].first){
				f[de[ii].first]=v[de[ii].first][de[ii].first][0];
				continue;
			}
			l=de[ii].first;r=de[ii].second;
			mid=(l+r)/2;
			for(i=l; i<=mid; i++) vv.push_back(i);
		}
		s=askk(vv);
		vv.push_back(1);
		ss=askk(vv);
		dele();
		cnt++;
		for(it=ss.begin(); it!=ss.end(); it++) fx[((*it)^f[1])]=cnt;
		for(ii=0; ii<e; ii++){
			if(de[ii].second==de[ii].first){
				continue;
			}
			l=de[ii].first;r=de[ii].second;
			mid=(l+r)/2;
			for(i=0; i<v[l][r].size(); i++){
				zx=(v[l][r][i]);
				if(fx[zx]==cnt){
					v[l][mid].push_back(zx);
				}else{
					v[mid+1][r].push_back(zx);
				}
			}
			de.push_back(make_pair(l,mid));
			de.push_back(make_pair(mid+1,r));
		}
		while(e>0){
			de.pop_front();e--;
		}
	}
	for(i=1; i<=a; i++) ans.push_back(f[i]);
  	if(ans.size()!=nn){
      for(i=1; ; i++) ;
    }
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::multiset<int> askk(std::vector<int>)':
Xoractive.cpp:13:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(i=0; i<w.size(); i++){
      |           ~^~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(i=0; i<v[l][r].size(); i++){
      |             ~^~~~~~~~~~~~~~~
Xoractive.cpp:85:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |    if(ans.size()!=nn){
      |       ~~~~~~~~~~^~~~

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