Submission #384351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384351	2021-04-01T12:56:12 Z	vanic	Xoractive (IZhO19_xoractive)	C++14	0 / 100	3 ms	620 KB

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;*/
	}
	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]);
		}
		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.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	492 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	620 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-