Submission #1186238

#TimeUsernameProblemLanguageResultExecution timeMemory
1186238yehudalesterCoreputer (IOI23_coreputer)C++20
90 / 100
5 ms908 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...