2277-XOR Circuit

問題文

解法

乱択．
どんどん答えを見つけていく感じ．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
unsigned int xor_shift(){
	static unsigned int x=clock(),y=362436069,z=521288629,w=88675123;
	unsigned int t;
	t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
int n ,k;
vector<int> correct;
string make_rand(string res){
	for(int i=0;i<n;i++){
		if(res[i]=='1')res[i]='0'+xor_shift()%2;
	}
	for(size_t i=0;i<correct.size();i++){
		res[correct[i]]='0';
	}
	return res;
}
string xor_string(const string &out,string res){
	for(int i=0;i<n;i++){
		if(out[i]=='1')res[i]=1-(res[i]-'0')+'0';
	}
	return res;
}
int check(const string &a){
	int ans=0,res=-1;
	for(int i=0;i<n;i++){
		if(a[i]=='1'){
			ans++;
			if(ans>1)return -1;
			res=i;
		}
	}
	return res;
}
int main(){
	cin>>n>>k;
	while(correct.size()<(size_t)k){
		string out=make_rand(string(n,'1'));
		cout<<"?"<<out<<endl;
		int in;
		cin>>in;
		if(in==0)continue;
		while(1){
			string next=make_rand(out);
			cout<<"?"<<next<<endl;
			cin>>in;
			if(in){
				out=next;
			}else{
				out=xor_string(out,next);
			}
			int v=check(out);
			if(v>=0){
				correct.push_back(v);
				break;
			}
		}
	}
	cout<<"!";
	sort(correct.begin(),correct.end());
	for(size_t i=0;i<correct.size();i++){
		if(i)cout<<" ";
		cout<<correct[i]+1;
	}
	cout<<endl;
	return 0;
}