Submission #1243038

#TimeUsernameProblemLanguageResultExecution timeMemory
1243038noyancanturkSphinx's Riddle (IOI24_sphinx)C++20
36 / 100
36 ms452 KiB
#include "sphinx.h" #include<bits/stdc++.h> using namespace std; const int lim=500; #define pb push_back #define ask perform_experiment int parent[lim]; int find(int i){ if(i==parent[i])return i; return parent[i]=find(parent[i]); } void unite(int i,int j){ parent[find(i)]=find(j); } vector<int>v[lim]; int n,m; int col[lim]; vector<int>find_colours(int N,vector<int>X,vector<int>Y) { n=N; vector<int>sp1,sp2; for(int i=0;i<n;i+=2){ sp1.pb(i); } for(int i=1;i<n;i+=2){ sp2.pb(i); } for(auto sp:{sp1,sp2}){ for(int c=0;c<n;c++){ auto guys=sp; while(guys.size()){ vector<int>toask(n,c); for(int j:guys)toask[j]=-1; int resthink=1; for(int i=0;i+1<n;i++)if(toask[i]!=toask[i+1])resthink++; int res=ask(toask); if(res==resthink){ break; } int l=0,r=int(guys.size())-2,ans=guys.size()-1; while(l<=r){ int mid=l+r>>1; toask=vector<int>(n,c); for(int j=0;j<=mid;j++){ toask[guys[j]]=-1; } resthink=1; for(int i=0;i+1<n;i++)if(toask[i]!=toask[i+1])resthink++; res=ask(toask); if(res==resthink){ l=mid+1; }else{ r=mid-1; ans=mid; } } ans=guys[ans]; reverse(guys.begin(),guys.end()); while(guys.back()!=ans)guys.pop_back(); guys.pop_back(); col[ans]=c; } } } return vector<int>(col,col+n); } // vector<int>find_colours(int N,vector<int>X,vector<int>Y) { // std::vector<int> E(N, -1); // int x = perform_experiment(E); // std::vector<int> G(N, 0); // if (x == 1) // G[0] = 1; // return G; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...