#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
if (a.empty()) return o << "{}";
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#include "grader.cpp"
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#include "chameleon.h"
#endif
const int mod = 1e9 + 7, N = 100000, logN = 20, K = 48763;
void Solve(int n) {
vector <vector <int>> g(n * 2 + 1), adj(n * 2 + 1);
vector <int> rem;
for (int i = 1; i <= 2 * n; ++i) {
rem.pb(i);
}
while (!rem.empty()) {
vector <int> left, right;
for (int i : rem) {
left.pb(i);
int nxt = Query(left);
left.pop_back();
if (nxt == left.size() + 1)
left.pb(i);
else
right.pb(i);
}
for (int i = 0; i < right.size(); ++i) {
int l = 0;
while (true) {
int r = left.size();
{
vector <int> now;
for (int i = l; i < r; ++i)
now.pb(right[i]);
int x = Query(now);
now.pb(left[i]);
int y = Query(now);
if (y > r - l)
break;
}
while (r - l > 1) {
int m = l + r >> 1;
vector <int> now;
for (int i = l; i < m; ++i)
now.pb(right[i]);
now.pb(left[i]);
int y = Query(now);
if (y <= m - l)
r = m;
else
l = m;
}
test(left[l], right[i]);
g[left[l]].pb(right[i]), g[right[i]].pb(left[l]), l++;
}
}
rem = right;
}
vector <int> pr(n * 2 + 1);
for (int i = 1; i <= n * 2; ++i) {
if (g[i].size() == 2) {
adj[i] = g[i];
} else if (g[i].size() == 3) {
if (Query({i, g[i][0], g[i][1]}) == 1)
adj[i].pb(g[i][2]);
else if (Query({i, g[i][0], g[i][2]}) == 1)
adj[i].pb(g[i][1]);
else
adj[i].pb(g[i][0]);
} else {
pr[i] = g[i][0];
}
}
vector <bool> vis_dfs(n * 2 + 1, false);
vector <int> cyc;
function <void(int)> dfs = [&](int v) {
vis_dfs[v] = true;
cyc.pb(v);
for (int u : adj[v]) if (!vis_dfs[u])
dfs(u);
};
vector <bool> vis(n * 2 + 1, false);
for (int i = 1; i <= n * 2; ++i) if (!vis_dfs[i]) {
int st = i;
cyc.clear(), dfs(st);
// check pair in the same cycle
int m = cyc.size();
for (int j = 0; j < m; ++j) if (g[cyc[j]].size() == 3) {
vector <int> now = g[cyc[j]];
{
auto it = find(all(now), cyc[(j + 1) % m]);
assert(it != now.end());
now.erase(it);
}
{
auto it = find(all(now), cyc[(j + m - 1) % m]);
assert(it != now.end());
now.erase(it);
}
pr[cyc[j]] = now[0];
}
}
for (int i = 1; i <= 2 * n; ++i) {
assert(pr[pr[i]] == i);
if (i < pr[i])
Answer(i, pr[i]);
}
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if (nxt == left.size() + 1)
| ~~~~^~~~~~~~~~~~~~~~~~
chameleon.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < right.size(); ++i) {
| ~~^~~~~~~~~~~~~~
chameleon.cpp:76:25: warning: unused variable 'x' [-Wunused-variable]
76 | int x = Query(now);
| ^
chameleon.cpp:83:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [6] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
44 ms |
644 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [6] |
| 3 |
Halted |
0 ms |
0 KB |
- |
