#include "chameleon.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,3>pi2;
//Query(vector<int>)
//Answer(int,int)
vector<int>adj[1005];
bool color[1005];
bool visited[1005];
void dfs(int index){
visited[index]=true;
//show(visit,index);
for(auto it:adj[index]){
if(visited[it]) continue;
color[it]=color[index]^1;
dfs(it);
}
}
pii f(int a, int b){
return {min(a,b),max(a,b)};
}
void Solve(int n){
for(int x=1;x<=2*n;x++){
memset(color,0,sizeof(color));
memset(visited,0,sizeof(visited));
for(int y=1;y<x;y++){
if(!visited[y]){
dfs(y);
}
}
//for(int y=1;y<=x;y++){
//cout << color[y] << " ";
//}
//cout << endl;
vector<int>v[2];
for(int y=1;y<x;y++){
v[color[y]].push_back(y);
}
for(int i=0;i<2;i++){
//identify all pairs
int last=0;
for(int j=0;j<3;j++){
int l=last;
int r=v[i].size()-1;
int best=r+1;
int mid;
while(l<=r){
mid=(l+r)/2;
vector<int>storage;
for(int k=last;k<=mid;k++){
storage.push_back(v[i][k]);
}
storage.push_back(x);
int hold=Query(storage);
if(hold!=(int)storage.size()){
best=mid;
r=mid-1;
}
else l=mid+1;
}
if(best==(int)v[i].size()) break;
last=best+1;
//show3(edgea,x,edgeb,v[i][best],i,i);
adj[x].push_back(v[i][best]);
adj[v[i][best]].push_back(x);
}
}
}
map<pii,int>mp;
for(int x=1;x<=2*n;x++){
if(adj[x].size()==1){
mp[f(x,adj[x][0])]++;
}
else if(adj[x].size()==3){
int hold=Query({x,adj[x][0],adj[x][1]});
int hold2=Query({x,adj[x][0],adj[x][2]});
if(hold==1){
mp[f(x,adj[x][0])]++;
mp[f(x,adj[x][1])]++;
}
else if(hold2==1){
mp[f(x,adj[x][0])]++;
mp[f(x,adj[x][2])]++;
}
else{
mp[f(x,adj[x][1])]++;
mp[f(x,adj[x][2])]++;
}
}
}
for(auto it:mp){
if(it.second==2){
//show2(a,it.first.first,b,it.first.second);
Answer(it.first.first,it.first.second);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
44 ms |
344 KB |
Output is correct |
| 4 |
Correct |
50 ms |
492 KB |
Output is correct |
| 5 |
Correct |
37 ms |
492 KB |
Output is correct |
| 6 |
Correct |
65 ms |
344 KB |
Output is correct |
| 7 |
Correct |
37 ms |
496 KB |
Output is correct |
| 8 |
Correct |
36 ms |
512 KB |
Output is correct |
| 9 |
Correct |
37 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
2 ms |
344 KB |
Output is correct |
| 13 |
Correct |
2 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
45 ms |
344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
44 ms |
344 KB |
Output is correct |
| 4 |
Correct |
50 ms |
492 KB |
Output is correct |
| 5 |
Correct |
37 ms |
492 KB |
Output is correct |
| 6 |
Correct |
65 ms |
344 KB |
Output is correct |
| 7 |
Correct |
37 ms |
496 KB |
Output is correct |
| 8 |
Correct |
36 ms |
512 KB |
Output is correct |
| 9 |
Correct |
37 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
1 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
2 ms |
344 KB |
Output is correct |
| 22 |
Correct |
2 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
1 ms |
344 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
0 ms |
344 KB |
Output is correct |
| 29 |
Correct |
1 ms |
344 KB |
Output is correct |
| 30 |
Incorrect |
45 ms |
344 KB |
Wrong Answer [3] |
| 31 |
Halted |
0 ms |
0 KB |
- |
