Submission #908548

#TimeUsernameProblemLanguageResultExecution timeMemory
908548amirhoseinfar1385Chameleon's Love (JOI20_chameleon)C++17
0 / 100
7 ms4952 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]; void createmos(){ for(int i=1;i<=n;i++){ allm[0].push_back(i); val[i]=0; } for(int i=n+1;i<=2*n;i++){ allm[1].push_back(i); val[i]=1; } } bool check(vector<int>now,int u){ now.push_back(u); int res=Query(now); if(res==(int)now.size()){ return 0; } return 1; } int findz(vector<int>now,int u){ 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+1;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++){ //cout<<i<<" "<<j<<" wtf "<<" "<<val[i]<<endl; 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(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); } } } } void Solve(int N) { n=N; createmos(); // cout<<"salam"<<endl; finde(); // cout<<"by"<<endl; 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...