#include "chameleon.h"
#include <iostream>
#include <vector>
using namespace std;
vector<int> A, B, E[1005];
int color[1005], q;
vector<int> adj;
vector<int> with(int u, vector<int> v)
{
v.emplace_back(u);
return v;
}
void find(int u, vector<int> v)
{
if(v.empty())
return;
if(v.size() == 1)
adj.emplace_back(v[0]);
else
{
int mid = v.size() / 2;
vector<int> l(v.begin(), v.begin() + mid), r(v.begin() + mid, v.end());
if(Query(with(u, l)) <= l.size())
find(u, l);
else
find(u, r);
}
}
vector<int> erase(vector<int> v, int u)
{
bool flag = 0;
for(int i = 0; i < v.size(); i++)
{
if(flag)
v[i - 1] = v[i];
if(v[i] == u)
flag = 1;
}
if(flag)
v.pop_back();
return v;
}
void dfs(int u)
{
for (auto v : E[u])
if(!color[v])
{
color[v] = 3 ^ color[u];
dfs(v);
}
}
void Solve(int N)
{
for (int i = 1; i <= 2 * N; i++)
{
for (int j = 1; j < i; j++)
color[j] = 0;
for (int j = 1; j < i; j++)
if(!color[j])
{
color[j] = 1;
dfs(j);
}
A.clear(), B.clear();
for (int j = 1; j < i; j++)
(color[j] == 1 ? A : B).emplace_back(j);
adj.clear();
while(Query(with(i, A)) <= A.size())
{
find(i, A);
A = erase(A, adj.back());
}
while(Query(with(i, B)) <= B.size())
{
find(i, B);
B = erase(B, adj.back());
}
for (int j : adj)
{
E[i].emplace_back(j);
E[j].emplace_back(i);
}
}
for (int i = 1; i <= 2 * N; i++)
if(E[i].size() == 3)
{
int a = E[i][0], b = E[i][1], c = E[i][2];
int x = Query(vector<int>{i, a, b}),
y = Query(vector<int>{i, b, c}),
z = 5 - x - y;
if(x == 2 && y == 2)
E[i].emplace_back(-b), E[b].emplace_back(-i);
else if(y == 2 && z == 2)
E[i].emplace_back(-c), E[c].emplace_back(-i);
else if(z == 2 && x == 2)
E[i].emplace_back(-a), E[a].emplace_back(-i);
}
else if(E[i].size() == 4)
{
int a = E[i][0], b = E[i][1], c = E[i][2];
int x;
if(E[i][3] == -a)
x = (Query(vector<int>{i, a, b}) == 2 ? b : c);
else if(E[i][3] == -b)
x = (Query(vector<int>{i, b, c}) == 2 ? c : a);
else
x = (Query(vector<int>{i, c, a}) == 2 ? a : b);
E[i].emplace_back(-x), E[x].emplace_back(-i);
}
for (int i = 1; i <= 2 * N; i++)
{
int sum = 0;
for(auto j : E[i])
sum += j;
if(i < sum)
Answer(i, sum);
}
}
Compilation message
chameleon.cpp: In function 'void find(int, std::vector<int>)':
chameleon.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(Query(with(u, l)) <= l.size())
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'std::vector<int> erase(std::vector<int>, int)':
chameleon.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(Query(with(i, A)) <= A.size())
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | while(Query(with(i, B)) <= B.size())
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
23 ms |
432 KB |
Output is correct |
4 |
Correct |
22 ms |
460 KB |
Output is correct |
5 |
Correct |
21 ms |
504 KB |
Output is correct |
6 |
Correct |
22 ms |
464 KB |
Output is correct |
7 |
Correct |
23 ms |
488 KB |
Output is correct |
8 |
Correct |
23 ms |
508 KB |
Output is correct |
9 |
Correct |
22 ms |
476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
280 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
2 ms |
336 KB |
Output is correct |
17 |
Correct |
2 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
44 ms |
440 KB |
Output is correct |
4 |
Correct |
46 ms |
424 KB |
Output is correct |
5 |
Correct |
44 ms |
412 KB |
Output is correct |
6 |
Correct |
45 ms |
464 KB |
Output is correct |
7 |
Correct |
46 ms |
464 KB |
Output is correct |
8 |
Correct |
47 ms |
432 KB |
Output is correct |
9 |
Correct |
44 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
23 ms |
432 KB |
Output is correct |
4 |
Correct |
22 ms |
460 KB |
Output is correct |
5 |
Correct |
21 ms |
504 KB |
Output is correct |
6 |
Correct |
22 ms |
464 KB |
Output is correct |
7 |
Correct |
23 ms |
488 KB |
Output is correct |
8 |
Correct |
23 ms |
508 KB |
Output is correct |
9 |
Correct |
22 ms |
476 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
0 ms |
336 KB |
Output is correct |
14 |
Correct |
0 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
336 KB |
Output is correct |
17 |
Correct |
0 ms |
336 KB |
Output is correct |
18 |
Correct |
0 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
280 KB |
Output is correct |
21 |
Correct |
1 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
2 ms |
336 KB |
Output is correct |
26 |
Correct |
2 ms |
336 KB |
Output is correct |
27 |
Correct |
1 ms |
336 KB |
Output is correct |
28 |
Correct |
0 ms |
336 KB |
Output is correct |
29 |
Correct |
0 ms |
336 KB |
Output is correct |
30 |
Correct |
44 ms |
440 KB |
Output is correct |
31 |
Correct |
46 ms |
424 KB |
Output is correct |
32 |
Correct |
44 ms |
412 KB |
Output is correct |
33 |
Correct |
45 ms |
464 KB |
Output is correct |
34 |
Correct |
46 ms |
464 KB |
Output is correct |
35 |
Correct |
47 ms |
432 KB |
Output is correct |
36 |
Correct |
44 ms |
456 KB |
Output is correct |
37 |
Correct |
45 ms |
616 KB |
Output is correct |
38 |
Correct |
22 ms |
552 KB |
Output is correct |
39 |
Correct |
43 ms |
540 KB |
Output is correct |
40 |
Correct |
43 ms |
464 KB |
Output is correct |
41 |
Correct |
46 ms |
464 KB |
Output is correct |
42 |
Correct |
23 ms |
508 KB |
Output is correct |
43 |
Correct |
45 ms |
408 KB |
Output is correct |
44 |
Correct |
44 ms |
544 KB |
Output is correct |
45 |
Correct |
46 ms |
484 KB |
Output is correct |