#include "chameleon.h"
#include <vector>
using namespace std;
vector<int> con[1005];
bool visit[1005];
bool answered[1005];
int l[1005];
int Query(const vector<int>& ys, int x, int s, int e)
{
vector<int> v = { x };
for (int i = s; i <= e; i++)
v.push_back(ys[i]);
return Query(v);
}
int Bisearch(const vector<int>& ys, int x, int l, int r, int d)
{
int lo = l, hi = r;
int res = -1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
int q = Query(ys, x, l, mid);
int sz = mid - l + 2;
if (q <= sz + d)
{
res = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
return res;
}
vector<int> xs;
vector<int> ys;
int color[1005];
void dfs(int root, int c)
{
if (color[root] != -1)
return;
color[root] = c;
for (auto& e : con[root])
dfs(e, (c + 1) % 2);
}
void Rebuild(int n)
{
// 1 .. i를 적절히 분류
memset(color, -1, sizeof(color));
for (int i = 1; i <= n; i++)
dfs(i, 0);
xs.clear();
ys.clear();
for (int i = 1; i <= n; i++)
{
if (color[i] == 0)
xs.push_back(i);
else
ys.push_back(i);
}
}
void Solve(int N)
{
for (int i = 1; i <= 2 * N; i++)
{
vector<int> over;
while (Query(xs, i, 0, (int)xs.size() - 1) != xs.size() + 1)
{
auto id = Bisearch(xs, i, 0, (int)xs.size() - 1, -1);
over.push_back(xs[id]);
xs.erase(xs.begin() + id);
}
while (Query(ys, i, 0, (int)ys.size() - 1) != ys.size() + 1)
{
auto id = Bisearch(ys, i, 0, (int)ys.size() - 1, -1);
over.push_back(ys[id]);
ys.erase(ys.begin() + id);
}
for (auto& o : over)
{
con[i].push_back(o);
con[o].push_back(i);
}
Rebuild(i);
}
for (int i = 1; i <= 2 * 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;
}
if (con[con[i][0]].size() == 1)
{
Answer(i, con[i][0]);
visit[i] = visit[con[i][0]] = true;
answered[i] = answered[con[i][0]] = true;
}
else if (con[con[i][1]].size() == 1)
{
Answer(i, con[i][1]);
visit[i] = visit[con[i][1]] = true;
answered[i] = answered[con[i][1]] = true;
}
else if (con[con[i][2]].size() == 1)
{
Answer(i, con[i][2]);
visit[i] = visit[con[i][2]] = true;
answered[i] = answered[con[i][2]] = true;
}
else
{
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);
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 <= 2 * 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
chameleon.cpp: In function 'void Rebuild(int)':
chameleon.cpp:62:2: error: 'memset' was not declared in this scope
62 | memset(color, -1, sizeof(color));
| ^~~~~~
chameleon.cpp:2:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
1 | #include "chameleon.h"
+++ |+#include <cstring>
2 | #include <vector>
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:85:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (Query(xs, i, 0, (int)xs.size() - 1) != xs.size() + 1)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
chameleon.cpp:92:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | while (Query(ys, i, 0, (int)ys.size() - 1) != ys.size() + 1)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
