This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace
{
vector<int> bad[1000];
int n;
int color[1000];
}
void dfs(int node, int C = 1)
{
color[node] = C;
for(auto it : bad[node])
if(!color[it])
dfs(it, 3 - C);
}
static void color_nodes()
{
memset(color, 0, sizeof(color));
int i;
for(i=1; i<=2*n; ++i)
if(!color[i])
dfs(i);
}
void add_edge(int x, int y)
{
bad[x].push_back(y);
bad[y].push_back(x);
}
void cbin(int node, const vector<int> &v)
{
int i, st, dr, mid;
st = 0; dr = v.size() - 1;
while(1)
{
vector<int> q;
for(i=st; i<=dr; ++i) q.push_back(v[i]);
q.push_back(node);
if(Query(q) == q.size()) return;
while(st < dr)
{
mid = (st + dr) / 2;
q.clear();
for(i=st; i<=mid; ++i) q.push_back(v[i]);
q.push_back(node);
if(Query(q) == q.size()) st = mid + 1;
else dr = mid;
}
add_edge(node, v[st]);
++st; dr = v.size() - 1;
}
}
static void find_bad()
{
int i, j;
for(i=1; i<=2*n; ++i)
{
color_nodes();
vector<int> A[2];
for(j=1; j<i; ++j)
A[color[j] - 1].push_back(j);
cbin(i, A[0]);
cbin(i, A[1]);
}
}
static void find_opposite()
{
color_nodes();
int i, j, k;
for(i=1; i<=2*n; ++i)
{
if(color[i] == 2) continue;
if(bad[i].size() == 1)
Answer(i, bad[i][0]);
else
{
assert(bad[i].size() == 3);
bool ok[3];
ok[0] = ok[1] = ok[2] = 1;
for(j=0; j<3; ++j)
for(k=j+1; k<3; ++k)
{
vector<int> vv = {i, bad[i][j], bad[i][k]};
if(Query(vv) == 1) ok[3 - j - k] = 0;
}
for(j=0; j<3; ++j)
{
int all[2], nr = 0;
for(auto it : bad[bad[i][j]])
if(it != i)
all[nr++] = it;
vector<int> vv = {bad[i][j], all[0], all[1]};
if(vv.back() == i) continue;
if(Query(vv) == 1) ok[j] = 0;
}
bool cnt = 0;
for(j=0; j<3; ++j) cnt += ok[j];
assert(cnt == 1);
for(j=0; j<3; ++j)
if(ok[j])
Answer(i, bad[i][j]);
}
}
}
void Solve(int N)
{
n = N;
find_bad();
find_opposite();
}
Compilation message (stderr)
chameleon.cpp: In function 'void cbin(int, const std::vector<int>&)':
chameleon.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Query(q) == q.size()) return;
~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:58:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(Query(q) == q.size()) st = mid + 1;
~~~~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |