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>
using namespace std;
vector<int> con[1005];
bool visit[1005];
bool answered[1005];
int l[1005];
int Query(int x, int s, int e)
{
vector<int> v = { x };
for (int i = s; i <= e; i++)
v.push_back(i);
return Query(v);
}
int Bisearch(int x, int l, int r, int d)
{
int lo = l, hi = r;
int res = 0;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
int q = Query(x, l, mid);
int sz = mid - l + 2;
if (q <= sz + d)
{
res = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
return res;
}
void Solve(int N)
{
for (int i = 1; i <= N; i++)
{
if (Query(i, N + 1, 2 * N) == N)
{
auto x = Bisearch(i, N + 1, 2 * N, -1);
con[i] = { x };
continue;
}
auto b = Bisearch(i, N + 1, 2 * N, -2);
auto a = Bisearch(i, N + 1, b - 1, -1);
if (Query(i, N + 1, a - 1) != a - N)
{
auto c = Bisearch(i, N + 1, a - 1, -1);
con[i] = { a, b, c };
}
else if (Query(i, a + 1, b - 1) != b - a)
{
auto c = Bisearch(i, a + 1, b - 1, -1);
con[i] = { a, b, c };
}
else
{
auto c = Bisearch(i, b + 1, 2 * N, -1);
con[i] = { a, b, c };
}
}
for (int i = 1; i <= N; i++)
{
if (visit[i])
continue;
if (con[i].size() == 1)
{
Answer(i, con[i][0]);
visit[i] = visit[con[i][0]] = true;
answered[i] = answered[con[i][0]] = true;
continue;
}
vector<int> a = { i, con[i][0], con[i][1] };
vector<int> b = { i, con[i][0], con[i][2] };
vector<int> c = { i, con[i][1], con[i][2] };
auto aq = Query(a);
auto bq = Query(b);
auto cq = Query(c);
if (aq == 1)
{
visit[i] = true;
l[i] = con[i][2];
}
else if (bq == 1)
{
visit[i] = true;
l[i] = con[i][1];
}
else
{
visit[i] = true;
l[i] = con[i][0];
}
}
for (int i = 1; i <= N; i++)
{
if (answered[i])
continue;
for (auto& c : con[i])
{
if (c == l[i] || l[c] == i || answered[c])
continue;
Answer(i, c);
answered[i] = answered[c] = true;
break;
}
}
}
Compilation message (stderr)
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:93:8: warning: unused variable 'cq' [-Wunused-variable]
93 | auto cq = Query(c);
| ^~
# | 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... |