#include <bits/stdc++.h>
using namespace std;
#include "chameleon.h"
vector<pair<int,int> > eds,adj[1005];
vector<int> st,v;
unordered_set<int> disj[2];
int vis[1005];
void change(int x, int g){
if(disj[g].find(x)==disj[g].end()) return;
disj[g].erase(x);
disj[g^1].insert(x);
v[x]=1;
for(auto i:adj[x]){
if(!v[i.first]) change(i.first,g^1);
}
}
void Solve(int n){
int x;
for(int i=1; i<=2*n; i++){
vector<int> ds;
for(int j:disj[0]) ds.push_back(j);
int lo=0,hi=(int)ds.size(),mid;
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
lo++,hi=(int)ds.size();
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
lo++,hi=(int)ds.size();
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
ds.clear();
for(int j:disj[1]) ds.push_back(j);
lo=0,hi=(int)ds.size();
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
for(int j=0; j<=500; j++) vis[j]=0;
change(ds[lo],1);
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
lo++,hi=(int)ds.size();
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
for(int j=0; j<=500; j++) vis[j]=0;
change(ds[lo],1);
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
lo++,hi=(int)ds.size();
while(lo<hi){
mid=(lo+hi)/2;
v.clear();
v.push_back(i);
for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
x=Query(v);
if(x<(int)v.size()) hi=mid;
else lo=mid+1;
}
if((int)ds.size()>lo){
for(int j=0; j<=500; j++) vis[j]=0;
change(ds[lo],1);
eds.push_back({ds[lo],i});
adj[i].push_back({ds[lo],eds.size()-1});
adj[ds[lo]].push_back({i,eds.size()-1});
st.push_back(0);
}
disj[1].insert(i);
}
for(int i=1; i<=2*n; i++){
if((int)adj[i].size()==1) continue;
assert((int)adj[i].size()==3);
int a=Query({i,adj[i][0].first,adj[i][1].first});
int b=Query({i,adj[i][0].first,adj[i][2].first});
int c=Query({i,adj[i][1].first,adj[i][2].first});
if(a==1) st[adj[i][2].second]=1;
if(b==1) st[adj[i][1].second]=1;
if(c==1) st[adj[i][0].second]=1;
}
for(int i=0; i<(int)eds.size(); i++){
if(st[i]==0) Answer(eds[i].first,eds[i].second);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
600 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
