#include "chameleon.h"
#include <utility>
#include <vector>
using namespace std;
using vi=vector<int>;
using pp=pair<int,int>;
using pvi=pair<vi,vi>;
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(t) ((int)((t).size()))
const int maxn2 = int(1e3) + 10;
int n;
vector<pvi> v;
vi graph[maxn2];
bool Search(int i, vi &v, int l, int r, bool must=false) {
if (l == r) return false;
if (!must) {
vi qry(v.begin()+l, v.begin()+r);
qry.push_back(i);
int qres = Query(qry);
if (qres == sz(qry)) return false;
}
if (l+1 == r) {
int j = v[l];
graph[i].pb(j); graph[j].pb(i);
return true;
}
int md = (l+r)/2;
Search(i, v, md, r, !Search(i, v, l, md));
return true;
}
void Rebuild(int p) {
static bool vis[maxn2], col[maxn2];
fill(vis+1, vis+p+1, 0);
fill(col+1, col+p+1, 0);
int vs = 0;
for (int i=1; i<=p; ++i) if (!vis[i]) {
static int q[maxn2], hd, tl;
hd = 0; tl = 1; q[0] = i; vis[i] = true;
if (sz(v) <= vs) v.resize(vs+1);
v[vs].first.clear();
v[vs].second.clear();
while (hd < tl) {
int x = q[hd++];
(col[x]?v[vs].second:v[vs].first).push_back(x);
for (int y:graph[x]) if (!vis[y]) {
vis[y] = true;
col[y] = !col[x];
q[tl++] = y;
}
}
++vs;
}
v.resize(vs);
}
void Solve(int N_) {
n = N_;
for (int i=1; i<=2*n; ++i) {
static vi lefts, rights;
lefts.clear(); rights.clear();
for (auto &tmp : v) {
lefts.insert(lefts.end(), all(tmp.first));
rights.insert(rights.end(), all(tmp.second));
}
bool found = Search(i, lefts, 0, sz(lefts));
found = Search(i, rights, 0, sz(rights)) || found;
if (!found) v.push_back({{i}, {}});
else Rebuild(i);
}
static bool is_directed[maxn2][maxn2];
for (int i=1; i<=2*n; ++i) {
if (sz(graph[i]) == 1) continue;
int a = graph[i][0], b = graph[i][1], c = graph[i][2];
int my_out = -1;
if (Query(vi{i, a, b}) == 1) my_out = c; else
if (Query(vi{i, b, c}) == 1) my_out = a; else
if (Query(vi{i, c, a}) == 1) my_out = b;
is_directed[i][my_out] = true;
is_directed[my_out][i] = true;
}
for (int i=1; i<=2*n; ++i) for (int j:graph[i]) {
if (i<j && !is_directed[i][j]) {
Answer(i, j);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
28 ms |
440 KB |
Output is correct |
| 4 |
Correct |
28 ms |
444 KB |
Output is correct |
| 5 |
Correct |
28 ms |
328 KB |
Output is correct |
| 6 |
Correct |
28 ms |
328 KB |
Output is correct |
| 7 |
Correct |
28 ms |
412 KB |
Output is correct |
| 8 |
Correct |
28 ms |
444 KB |
Output is correct |
| 9 |
Correct |
29 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
328 KB |
Output is correct |
| 7 |
Correct |
0 ms |
328 KB |
Output is correct |
| 8 |
Correct |
0 ms |
328 KB |
Output is correct |
| 9 |
Correct |
0 ms |
328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
328 KB |
Output is correct |
| 7 |
Correct |
0 ms |
328 KB |
Output is correct |
| 8 |
Correct |
0 ms |
328 KB |
Output is correct |
| 9 |
Correct |
0 ms |
328 KB |
Output is correct |
| 10 |
Correct |
1 ms |
328 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
1 ms |
328 KB |
Output is correct |
| 17 |
Correct |
1 ms |
328 KB |
Output is correct |
| 18 |
Correct |
1 ms |
328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
1344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
28 ms |
440 KB |
Output is correct |
| 4 |
Correct |
28 ms |
444 KB |
Output is correct |
| 5 |
Correct |
28 ms |
328 KB |
Output is correct |
| 6 |
Correct |
28 ms |
328 KB |
Output is correct |
| 7 |
Correct |
28 ms |
412 KB |
Output is correct |
| 8 |
Correct |
28 ms |
444 KB |
Output is correct |
| 9 |
Correct |
29 ms |
432 KB |
Output is correct |
| 10 |
Correct |
0 ms |
328 KB |
Output is correct |
| 11 |
Correct |
0 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
0 ms |
328 KB |
Output is correct |
| 14 |
Correct |
0 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
0 ms |
328 KB |
Output is correct |
| 17 |
Correct |
0 ms |
328 KB |
Output is correct |
| 18 |
Correct |
0 ms |
328 KB |
Output is correct |
| 19 |
Correct |
1 ms |
328 KB |
Output is correct |
| 20 |
Correct |
1 ms |
328 KB |
Output is correct |
| 21 |
Correct |
1 ms |
328 KB |
Output is correct |
| 22 |
Correct |
1 ms |
328 KB |
Output is correct |
| 23 |
Correct |
1 ms |
328 KB |
Output is correct |
| 24 |
Correct |
1 ms |
328 KB |
Output is correct |
| 25 |
Correct |
1 ms |
328 KB |
Output is correct |
| 26 |
Correct |
1 ms |
328 KB |
Output is correct |
| 27 |
Correct |
1 ms |
328 KB |
Output is correct |
| 28 |
Correct |
0 ms |
328 KB |
Output is correct |
| 29 |
Correct |
0 ms |
328 KB |
Output is correct |
| 30 |
Incorrect |
56 ms |
1344 KB |
Wrong Answer [3] |
| 31 |
Halted |
0 ms |
0 KB |
- |
