Submission #384369

#	Time	Username	Problem	Language	Result	Execution time	Memory
384369		vanic	Xoractive (IZhO19_xoractive)	C++14	0 / 100	4 ms	748 KiB

Xoractive

#include "interactive.h"
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#include <cassert>

using namespace std;

const int Log=7;

vector < int > sol;
vector < int > q;
vector < int > odg1, odg2;
vector < int > komp;
vector < int > val[Log];

vector < int > tren;

void probaj(int x){
	int pos;
	for(int i=0; i<Log; i++){
		if((1<<i)&x){
			if(tren.empty()){
				tren=val[i];
			}
			else{
				pos=0;
				for(int j=0; j<(int)tren.size(); j++){
					while(pos<(int)val[i].size() && val[i][pos]<tren[j]){
						pos++;
					}
//					cout << val[i][pos] << endl;
					if(pos>=(int)val[i].size() || tren[j]!=val[i][pos]){
//						cout << "brisem " << j << endl;
						tren.erase(tren.begin()+j);
						j--;
					}
					else{
						pos++;
					}
				}
			}
		}
/*		for(int i=0; i<tren.size(); i++){
			cout << tren[i] << ' ';
		}
		cout << endl;*/
	}
	while(tren.size()>1 && tren.back()==tren[0]){
		tren.pop_back();
	}
//	assert(!tren.empty());
	if(tren.size()>1){
		tren={ask(x+1)};
	}
//	assert(tren.size()==1);
	for(int i=0; i<Log; i++){
		if((1<<i)&x){
			val[i].erase(find(val[i].begin(), val[i].end(), tren[0]));
		}
	}
	sol[x]=tren[0];
	tren.clear();
}

vector < int > guess(int n){
	sol.resize(n, 0);
	sol[0]=ask(1);
	int sz;
	for(int j=0; j<Log; j++){
		for(int i=1; i<n; i++){
			if(i&(1<<j)){
				q.push_back(i+1);
			}
		}
		if(q.empty()){
			break;
		}
		odg2=get_pairwise_xor(q);
		q.push_back(1);
		odg1=get_pairwise_xor(q);
		q.clear();
		int pos1=0, pos2=0;
		for(int i=0; i<(int)odg1.size(); i++){
			if(pos2<(int)odg2.size() && odg1[pos1]==odg2[pos2]){
				pos1++;
				pos2++;
			}
			else{
				komp.push_back(odg1[pos1]);
				pos1++;
			}
		}
/*		for(int i=0; i<komp.size(); i++){
			cout << komp[i] << ' ';
		}
		cout << endl;*/
		komp.erase(komp.begin());
		sz=komp.size();
		for(int i=0; i<sz/2; i++){
			komp.erase(komp.begin()+i);
		}
		for(int i=0; i<(int)komp.size(); i++){
			val[j].push_back(sol[0]^komp[i]);
//			cout << val[j].back() << ' ';
		}
//		cout << endl;*/
		komp.clear();
	}
//	cout << endl;
	for(int i=n-1; i>0; i--){
		probaj(i);
	}
/*	for(int i=0; i<n; i++){
		cout << sol[i] << ' ';
	}
	cout << endl;*/
	return sol;
}

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