#include "chameleon.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
namespace {
const int maxn = 1024;
vector<int> A[maxn];
int query(vector<int> vec)
{
for (int &x : vec)
x += 1;
return Query(vec);
}
bool bin_query(int v, vector<int> vec, int l, int r)
{
vector<int> dard = vector<int>(&vec[l], &vec[r]); // UB but whatever
dard.push_back(v);
return query(dard) != dard.size();
}
int bin(int v, vector<int> vec)
{
int l = 0, r = vec.size();
if (l == r)
return -1;
if (!bin_query(v, vec, l, r))
return -1;
while (r - l > 1) {
int m = (l + r)/2;
if (!bin_query(v, vec, l, m))
l = m;
else
r = m;
}
return l;
}
bool vis[maxn];
void dfs(int v, int col, vector<int> vec[2])
{
vis[v] = 1;
vec[col].push_back(v);
for (int u : A[v]) {
if (!vis[u])
dfs(u, 1-col, vec);
}
}
void solve(int v)
{
if (v == 0)
return;
solve(v-1);
memset(vis, 0, v);
vector<int> vec[2];
Loop (u,0,v) {
if (vis[u])
continue;
dfs(u, 0, vec);
}
Loop (col, 0, 2) {
int i;
while ((i = bin(v, vec[col])) != -1) {
int u = vec[col][i];
swap(vec[col][i], vec[col].back());
vec[col].pop_back();
A[v].push_back(u);
A[u].push_back(v);
}
}
}
int love[maxn];
int match[maxn];
} // namespace
void Solve(int N)
{
solve(2*N-1);
//Loop (i,0,2*N) {
// cerr << i << ": ";
// for (int j : A[i])
// cerr << j << ' ';
// cerr << '\n';
//}
memset(love, -1, sizeof(love));
Loop (v,0,2*N) {
if (A[v].size() == 1)
continue;
assert(A[v].size() == 3);
int a = A[v][0];
int b = A[v][1];
int c = A[v][2];
//cerr << v << ": " << v << ' ' << a << ' ' << b << ' ' << c << " - " << query({v, a, c}) << '\n';
if (query({v, a, b}) == 1)
love[v] = c;
else if (query({v, a, c}) == 1)
love[v] = b;
else
love[v] = a;
}
//Loop (i,0,2*N)
// cerr << love[i]+1 << ' ';
//cerr << '\n';
Loop (v,0,2*N) {
if (A[v].size() == 1) {
match[v] = A[v][0];
continue;
}
int a = A[v][0];
int b = A[v][1];
int c = A[v][2];
if (love[a] != v && love[v] != a)
match[v] = a;
else if (love[b] != v && love[v] != b)
match[v] = b;
else
match[v] = c;
}
//Loop (i,0,2*N)
// cerr << match[i] << ' ';
//cerr << '\n';
Loop (i,0,2*N) {
if (i > match[i])
continue;
Answer(i+1, match[i]+1);
}
}
Compilation message
chameleon.cpp: In function 'bool {anonymous}::bin_query(int, std::vector<int>, int, int)':
chameleon.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | return query(dard) != dard.size();
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:106:14: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
106 | if (query({v, a, b}) == 1)
| ^
chameleon.cpp:106:14: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
chameleon.cpp:108:19: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
108 | else if (query({v, a, c}) == 1)
| ^
chameleon.cpp:108:19: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
# |
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 |
22 ms |
720 KB |
Output is correct |
4 |
Correct |
23 ms |
692 KB |
Output is correct |
5 |
Correct |
22 ms |
708 KB |
Output is correct |
6 |
Correct |
22 ms |
720 KB |
Output is correct |
7 |
Correct |
22 ms |
716 KB |
Output is correct |
8 |
Correct |
23 ms |
688 KB |
Output is correct |
9 |
Correct |
23 ms |
824 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 |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
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 |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 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 |
376 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
2 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 |
47 ms |
696 KB |
Output is correct |
4 |
Correct |
46 ms |
704 KB |
Output is correct |
5 |
Correct |
46 ms |
592 KB |
Output is correct |
6 |
Correct |
48 ms |
704 KB |
Output is correct |
7 |
Correct |
47 ms |
700 KB |
Output is correct |
8 |
Correct |
46 ms |
704 KB |
Output is correct |
9 |
Correct |
46 ms |
704 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 |
22 ms |
720 KB |
Output is correct |
4 |
Correct |
23 ms |
692 KB |
Output is correct |
5 |
Correct |
22 ms |
708 KB |
Output is correct |
6 |
Correct |
22 ms |
720 KB |
Output is correct |
7 |
Correct |
22 ms |
716 KB |
Output is correct |
8 |
Correct |
23 ms |
688 KB |
Output is correct |
9 |
Correct |
23 ms |
824 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 |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
0 ms |
336 KB |
Output is correct |
16 |
Correct |
0 ms |
336 KB |
Output is correct |
17 |
Correct |
0 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
336 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 |
376 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
2 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 |
47 ms |
696 KB |
Output is correct |
31 |
Correct |
46 ms |
704 KB |
Output is correct |
32 |
Correct |
46 ms |
592 KB |
Output is correct |
33 |
Correct |
48 ms |
704 KB |
Output is correct |
34 |
Correct |
47 ms |
700 KB |
Output is correct |
35 |
Correct |
46 ms |
704 KB |
Output is correct |
36 |
Correct |
46 ms |
704 KB |
Output is correct |
37 |
Correct |
45 ms |
684 KB |
Output is correct |
38 |
Correct |
22 ms |
700 KB |
Output is correct |
39 |
Correct |
46 ms |
700 KB |
Output is correct |
40 |
Correct |
46 ms |
832 KB |
Output is correct |
41 |
Correct |
47 ms |
704 KB |
Output is correct |
42 |
Correct |
23 ms |
720 KB |
Output is correct |
43 |
Correct |
50 ms |
704 KB |
Output is correct |
44 |
Correct |
46 ms |
596 KB |
Output is correct |
45 |
Correct |
46 ms |
712 KB |
Output is correct |