Submission #1186232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186232		yehudalester	Coreputer (IOI23_coreputer)	C++20	20 / 100	2 ms	1088 KiB

coreputer

#include "coreputer.h"
#include<vector>
#include<numeric>
#include<random>
#include<chrono>
using namespace std;
using ll=int;
using vll=vector<ll>;
using pll=pair<ll,ll>;
vll to_vector(ll x, ll n){
	vll vec;
	while(n--){
		vec.push_back(x%2);
		x/=2;
	}
	return vec;
}
vll vect(ll x){
	vll res;
	for(ll i=0;i<32;i++){
		if(x&(1<<i)){
			res.push_back(i);
		}
	}
	return res;
}
std::vector<int> malfunctioning_cores(int N) {
	vll vec((1<<N)-1);
	iota(vec.begin(),vec.end(),1);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<pll> past;
	while(vec.size()!=1){
		ll c=0;
		l:
		ll x=0;
		for(ll i=0;i<N;i++){
			if(uniform_int_distribution<ll>(0,1)(rng)){
				x^=(1<<i);
			}
		}
		if(x==0||x==(1<<N)-1){
			goto l;
		}
		for(pll p:past){
			if(x&p.first==x&&p.second==-1){
				goto l;
			}
			if(x&p.first==p.first&&p.second==-1){
				goto l;
			}
		}
		ll x1=0,x2=0,x3=0;
		if(vec.size()<1000){
		for(ll y:vec){
				if(__builtin_popcount(y&x)>__builtin_popcount(y&(~x))){
					x1++;
				}
				if(__builtin_popcount(y&x)==__builtin_popcount(y&(~x))){
					x2++;
				}
				if(__builtin_popcount(y&x)<__builtin_popcount(y&(~x))){
					x3++;
				}
		}
		double p1=double(x1)/(x1+x3),p2=double(x3)/(x1+x3);
		if((x1==0||x3==0||-(p1*log(p1)+p2*log(p2))<0.5)&&c++<3){
			goto l;
		}
		}
		vll t;
		ll res=run_diagnostic(vect(x));
		for(ll y:vec){
			if(res==1){
				if(__builtin_popcount(y&x)>__builtin_popcount(y&(~x))){
					t.push_back(y);
				}
			}
			if(res==0){
				if(__builtin_popcount(y&x)==__builtin_popcount(y&(~x))){
					t.push_back(y);
				}
			}
			if(res==-1){
				if(__builtin_popcount(y&x)<__builtin_popcount(y&(~x))){
					t.push_back(y);
				}
			}
		}
		vec=t;
		past.push_back({x,res});
	}
	return to_vector(vec[0],N);
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40