Submission #908593

#TimeUsernameProblemLanguageResultExecution timeMemory
908593amirhoseinfar1385Chameleon's Love (JOI20_chameleon)C++17
100 / 100
42 ms852 KiB
#include "chameleon.h" #include<bits/stdc++.h> using namespace std; const int maxn=1000+10; int n,val[maxn]; vector<int>adj[maxn]; map<pair<int,int>,int>mp; vector<int>allm[4]; bool check(vector<int>now,int u){ now.push_back(u); if((int)now.size()==0){ return 0; } int res=Query(now); if(res==(int)now.size()){ return 0; } return 1; } void createmos(){ for(int i=1;i<=2*n;i++){ while(check(allm[val[i]],i)){ val[i]++; } allm[val[i]].push_back(i); } } int findz(vector<int>now,int u){ // cout<<(int)now.size()<<" "<<u<<endl; if((int)now.size()==1){ return now[0]; } int m=(int)now.size(); m>>=1; vector<int>left,right; for(int i=0;i<m;i++){ left.push_back(now[i]); } for(int i=m;i<(int)now.size();i++){ right.push_back(now[i]); } if(check(left,u)){ return findz(left,u); } return findz(right,u); } void finde(){ for(int i=1;i<=2*n;i++){ for(int j=0;j<4;j++){ if(j==val[i]){ continue; } vector<int>tof=allm[j]; sort(tof.begin(),tof.end()); for(auto x:adj[i]){ int p=lower_bound(tof.begin(),tof.end(),x)-tof.begin(); if(p!=(int)tof.size()&&tof[p]==x){ tof.erase(tof.begin()+p); } } while((int)adj[i].size()<3&&check(tof,i)){ int res=findz(tof,i); int p=lower_bound(tof.begin(),tof.end(),res)-tof.begin(); tof.erase(tof.begin()+p); adj[i].push_back(res); adj[res].push_back(i); mp[make_pair(min(i,res),max(i,res))]=1; } } } } void Solve(int N) { n=N; createmos(); finde(); for(int i=1;i<=2*n;i++){ if(adj[i].size()==3){ int res=Query({i,adj[i][0],adj[i][1]}); if(res==1){ mp[make_pair(min(i,adj[i][2]),max(i,adj[i][2]))]=0; } res=Query({i,adj[i][0],adj[i][2]}); if(res==1){ mp[make_pair(min(i,adj[i][1]),max(i,adj[i][1]))]=0; } res=Query({i,adj[i][2],adj[i][1]}); if(res==1){ mp[make_pair(min(i,adj[i][0]),max(i,adj[i][0]))]=0; } } } for(auto x:mp){ if(x.second==1){ // cout<<x.first.first<<" "<<x.first.second<<endl; Answer(x.first.first,x.first.second); } } }
#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...