Submission #223108

#TimeUsernameProblemLanguageResultExecution timeMemory
223108Andrei_CotorChameleon's Love (JOI20_chameleon)C++14
0 / 100
5 ms384 KiB
//o pereche de 2 cameleoni (x,y) va da rasp 1 daca: color(x)=color(y), x il iubeste pe y, y il iubeste pe x //impart in 4 seturi a.i. cameleonii din cele 4 seturi sunt independenti #include"chameleon.h" #include<vector> #include<iostream> using namespace std; vector<int> Sets[4]; vector<int> Adj[1005]; bool Answered[1005]; int Loves[1005],Loved[1005]; //loves=pe cine, loved=de cine bool Viz[1005]; int nrq; bool check(int cham, int s, int st, int dr) { if(st>dr) return 0; vector<int> Aux; Aux.push_back(cham); for(int j=st; j<=dr; j++) Aux.push_back(Sets[s][j]); nrq++; if(Query(Aux)==Aux.size()) return 0; return 1; } int getCandidate(int cham, int s, int dec) { int poz=dec-1; for(int i=9; i>=0; i--) { if(poz+(1<<i)<Sets[s].size() && !check(cham,s,dec,poz+(1<<i))) poz+=(1<<i); } poz++; return poz; } void Solve(int n) { for(int i=1; i<=2*n; i++) { int ind=-1; for(int j=0; j<4; j++) { Sets[j].push_back(i); if(Query(Sets[j])==Sets[j].size()) { if(ind==-1 || Sets[j].size()<Sets[ind].size()) //le echilibrez cat mai mult pt a optimiza nr de pasi de la cautare ind=j; } Sets[j].pop_back(); } Sets[ind].push_back(i); } for(int i=0; i<4; i++) { for(auto cham:Sets[i]) { int nr=0; for(int j=i+1; j<4; j++) { int lastcand=-1; while(nr<3) { if(!check(cham,j,lastcand+1,Sets[j].size()-1)) break; int cand=getCandidate(cham,j,lastcand+1); if(cand==Sets[j].size()) break; nr++; Adj[cham].push_back(Sets[j][cand]); Adj[Sets[j][cand]].push_back(cham); lastcand=cand; } if(nr==3) break; } } } cout<<nrq<<"\n"; for(int i=1; i<=2*n; i++) { if(Answered[i]) continue; if(Adj[i].size()==1) //i iubeste si este iubit de acelasi cameleon, deci cel din Adj este cel de aceasi culoare { Answer(i,Adj[i][0]); Answered[i]=1; Answered[Adj[i][0]]=1; } } vector<int> Aux; for(int ind=1; ind<=2*n; ind++) { int i=ind; while(!Viz[i]) { Viz[i]=1; if(Adj[i].size()==1) continue; Aux.clear(); Aux.push_back(i); Aux.push_back(Adj[i][0]); Aux.push_back(Adj[i][1]); if(Loved[i]!=Adj[i][2] && Query(Aux)==1) { Loves[i]=Adj[i][2]; Loved[Adj[i][2]]=i; i=Loves[i]; continue; } Aux[2]=Adj[i][2]; if(Loved[i]!=Adj[i][1] && Query(Aux)==1) { Loves[i]=Adj[i][1]; Loved[Adj[i][1]]=i; i=Loves[i]; continue; } Aux[1]=Adj[i][1]; if(Loved[i]!=Adj[i][0] && Query(Aux)==1) { Loves[i]=Adj[i][0]; Loved[Adj[i][0]]=i; i=Loves[i]; continue; } } } for(int i=1; i<=2*n; i++) { if(Answered[i]) continue; int per=Adj[i][0]^Adj[i][1]^Adj[i][2]^Loves[i]^Loved[i]; Answer(i,per); Answered[per]=1; Answered[i]=1; } }

Compilation message (stderr)

chameleon.cpp: In function 'bool check(int, int, int, int)':
chameleon.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(Query(Aux)==Aux.size())
     ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'int getCandidate(int, int, int)':
chameleon.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(poz+(1<<i)<Sets[s].size() && !check(cham,s,dec,poz+(1<<i)))
      ~~~~~~~~~~^~~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(Sets[j])==Sets[j].size())
       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
chameleon.cpp:80:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(cand==Sets[j].size())
         ~~~~^~~~~~~~~~~~~~~~
#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...