Submission #1186237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186237		yehudalester	Coreputer (IOI23_coreputer)	C++20	90 / 100	5 ms	908 KiB

coreputer

#include "coreputer.h"
#include<vector>
#include<numeric>
#include<random>
#include<chrono>
#include<cmath>
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;
}
ll pick(vll vec, ll N){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	pair<double,ll> res;
	for(ll cnt=0;cnt<5;cnt++){
		ll x=0;
		for(ll i=0;i<N;i++){
			if(uniform_int_distribution<ll>(0,1)(rng)){
				x^=(1<<i);
			}
		}
		ll x1=0,x2=0,x3=0;
		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+x2+x3),p2=double(x2)/(x1+x2+x3),p3=double(x3)/(x1+x2+x3);
		double r1=(abs(p1)<1e-9?0:p1*log(p1)),r2=(abs(p2)<1e-9?0:p2*log(p2)),r3=(abs(p3)<1e-9?0:p3*log(p3));
		res=max(res,{-r1-r2-r3,x});	
	}
	return res.second;
}
std::vector<int> malfunctioning_cores(int N) {
	vll vec((1<<N)-1);
	iota(vec.begin(),vec.end(),1);
	vector<pll> past;
	while(vec.size()!=1){
		ll x=pick(vec,N);
		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: 40 / 40
• Subtask 3: 30 / 40