#include <bits/stdc++.h>
#define pb push_back
#include "chameleon.h"
using namespace std;
const int maxN = 1e3 + 10;
vector<int> G[maxN];
vector<int> V[2], P;
int mk[maxN];
void DFS(int u, int d){
V[d].pb(u);
mk[u] = 1;
for(auto adj : G[u]) if(!mk[adj]) DFS(adj, d ^ 1);
}
int Find(int c, int id){
int l = 0, r = V[c].size();
int mid;
while(l + 1 < r){
mid = (l + r) >> 1;
P.clear();
for(int i = mid; i < (int) V[c].size(); i++) P.pb(V[c][i]);
P.pb(id);
if(Query(P) == P.size()) r = mid;
else l = mid;
}
return l;
}
void AddE(int u, int v){
G[u].pb(v);
G[v].pb(u);
}
void RemE(int u, int v){
auto it = G[u].begin();
while((it != G[u].end()) && (*it != v)) it ++;
if(it != G[u].end()) G[u].erase(it);
it = G[v].begin();
while((it != G[v].end()) && (*it != u)) it ++;
if(it != G[v].end()) G[v].erase(it);
}
void Solve(int n){
for(int i = 1; i <= n + n; i++) G[i].clear();
for(int i = 1; i <= n + n; i++){
V[0].clear(); V[1].clear();
memset(mk, 0, sizeof mk);
for(int nd = 1; nd < i; nd ++) if(!mk[nd]) DFS(nd, 0);
for(int it = 0; it < 2; it ++){
while(true){
P = V[it];
P.pb(i);
if(Query(P) == P.size()) break;
int res = Find(it, i);
AddE(i, V[it][res]);
V[it].erase(V[it].begin() + res);
}
}
}
/*
cerr << "! ";
for(int i = 1; i <= n + n; i++) cerr << G[i].size() << ' ';
cerr << '\n';
*/
vector< pair<int, int> > ans;
vector< pair<int, int> > RE;
for(int i = 1; i <= n + n; i++){
//assert(G[i].size() != 2);
int re;
if(G[i].size() == 3){
P = {i, G[i][0], G[i][1]};
if(Query(P) == 1) re = G[i][2];
else {
P = {i, G[i][2], G[i][1]};
if(Query(P) == 1) re = G[i][0];
else re = G[i][1];
}
}
RE.pb({re, i});
//cerr << "# " << re << ' ' << i << '\n';
}
for(auto x : RE) RemE(x.first, x.second);
while(ans.size() < n){
int ru = -1, rv = -1;
for(int i = 1; i <= n + n; i++){
if(G[i].size() == 1){
ru = i;
rv = G[i][0];
break;
}
}
if(ru != -1){
ans.pb({ru, rv});
RemE(ru, rv);
continue;
}
break;
}
for(auto x : ans) Answer(x.first, x.second);
}
/*
4
0 0 0 0 1 1 1 1
4 3 2 1 2 3 4 1
6 8 7 5 2 3 4 1
4
1 1 1 0 0 1 0 0
3 1 4 3 1 2 2 4
5 7 4 3 1 8 2 6
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
*/
Compilation message
chameleon.cpp: In function 'int Find(int, int)':
chameleon.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Query(P) == P.size()) r = mid;
~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Query(P) == P.size()) break;
~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ans.size() < n){
~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
