Submission #341431

#	Time	Username	Problem	Language	Result	Execution time	Memory
341431		ogibogi2004	Xoractive (IZhO19_xoractive)	C++14	100 / 100	7 ms	756 KiB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
set<int>seen[8];
set<int>used;
int ans[128],n1;
void rec(int idx,int p,set<int>a)
{
	//cout<<idx<<" "<<p<<endl;
	if(p==7)
	{
		if(idx==0)return;
		for(auto xd:a)
		{
			if(used.find(xd)!=used.end())continue;
			ans[idx]=xd;
			used.insert(xd);
			break;
		}
		return;
	}
	if(idx+(1<<p)<n1)
	{
		set<int>a1;
		for(auto xd:a)
		{
			if(seen[p].find(xd)!=seen[p].end())
			{
				a1.insert(xd);
			}
		}
		rec(idx+(1<<p),p+1,a1);
	}
	rec(idx,p+1,a);
	
}
vector<int> guess(int n) {
	memset(ans,-1,sizeof(ans));
	ans[0]=ask(1);n1=n;
	//cout<<"*1\n";
	for(int i=0;i<7;i++)
	{
		vector<int>v;
		for(int j=1;j<n;j++)
		{
			if(j&(1<<i))v.push_back(j+1);
		}
		vector<int> t1;
		if(v.size()>0)t1=get_pairwise_xor(v);
		v.push_back(1);
		vector<int> t2=get_pairwise_xor(v);
		multiset<int>ms;
		for(int j=0;j<t2.size();j++)
		{
			ms.insert(t2[j]);
		}
		for(int j=0;j<t1.size();j++)
		{
			ms.erase(ms.find(t1[j]));
		}
		for(auto k:ms)if(k!=0)seen[i].insert(k^ans[0]);
	}
	//cout<<"*2\n";
	set<int>ivan;
	for(int i=0;i<7;i++)
	{
		for(auto xd:seen[i])ivan.insert(xd);
	}
	rec(0,0,ivan);
	//cout<<"*3\n";
	vector<int>ret;
	for(int i=0;i<n;i++)
	{
		//cout<<ans[i]<<" ";
		ret.push_back(ans[i]);
	}
	//cout<<endl;
	return ret;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int j=0;j<t2.size();j++)
      |               ~^~~~~~~~~~
Xoractive.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0;j<t1.size();j++)
      |               ~^~~~~~~~~~

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