#include "chameleon.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
const int MAXN = 500 + 10;
namespace
{
int n;
int perm[MAXN];
int before[MAXN];
bool found[2 * MAXN];
std::vector <int> candidates[MAXN];
std::vector <int> x, y;
}
int runBinaryX(int fromPos, int idx)
{
int l = fromPos - 1, r = n, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> curr;
curr.push_back(x[idx]);
// std::cout << "Add: " << x[idx] << '\n';
for (int j = fromPos ; j <= mid ; ++j)
{
// std::cout << "add: " << y[j] << '\n';
curr.push_back(y[j]);
}
if (Query(curr) == curr.size()) l = mid;
else r = mid;
}
return r;
}
int runBinaryY(int fromPos, int idx)
{
int l = fromPos - 1, r = n, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> curr;
curr.push_back(y[idx]);
// std::cout << "Add: " << x[idx] << '\n';
for (int j = fromPos ; j <= mid ; ++j)
{
// std::cout << "add: " << y[j] << '\n';
if (x[j] != before[y[idx]]) curr.push_back(x[j]);
}
if (Query(curr) == curr.size()) l = mid;
else r = mid;
}
return r;
}
void Solve(int n)
{
::n = n;
x.resize(n);
y.resize(n);
std::iota(x.begin(), x.end(), 1);
std::iota(y.begin(), y.end(), n + 1);
// std::cout << "x, y: \n";
// for (const int &i : x) std::cout << i << ' '; std::cout << '\n';
// for (const int &i : y) std::cout << i << ' '; std::cout << '\n';
// for (int i = 1 ; i <= 2 * n ; ++i)
// {
// for (int j = 1 ; j <= 2 * n ; ++j)
// {
// if (i == j)
// {
// continue;
// }
// if (Query({i, j}) == 1)
// {
// // std::cout << "here: " << i << ' ' << j << '\n';
// candidates[i].push_back(j);
// }
// }
// if (candidates[i].size() == 3)
// {
// if (Query({candidates[i][0], candidates[i][2], i}) == 1)
// {
// std::swap(candidates[i].back(), candidates[i][1]);
// } else if (Query({candidates[i][1], candidates[i][2], i}) == 1)
// {
// std::swap(candidates[i].back(), candidates[i][0]);
// }
// candidates[i].pop_back();
// }
// std::cout << "size: " << i << ' ' << candidates[i].size() << '\n';
// for (const int &j : candidates[i]) std::cout << j << ' '; std::cout << '\n';
// }
for (int i = 0 ; i < n ; ++i)
{
int lastAdded = -1;
std::vector <int> added;
for (int j = 0 ; j < 3 && lastAdded + 1 < n ; ++j)
{
int curr = runBinaryX(lastAdded + 1, i);
if (curr != n)
{
candidates[x[i]].push_back(y[curr]);
}
lastAdded = curr;
}
if (candidates[x[i]].size() == 3)
{
if (Query({candidates[x[i]][0], candidates[x[i]][2], x[i]}) == 1)
{
std::swap(candidates[x[i]].back(), candidates[x[i]][1]);
} else if (Query({candidates[x[i]][1], candidates[x[i]][2], x[i]}) == 1)
{
std::swap(candidates[x[i]].back(), candidates[x[i]][0]);
}
// std::cout << "before: " << candidates[x[i]].back() << " = " << x[i] << '\n';
before[candidates[x[i]].back()] = x[i];
candidates[x[i]].pop_back();
} else
{
assert(candidates[x[i]].size() == 1);
Answer(x[i], candidates[x[i]].back());
found[candidates[x[i]].back()] = true;
found[x[i]] = true;
}
// std::cout << "candidates: " << x[i] << '\n';
// for (const int &idx : candidates[x[i]])
// {
// std::cout << idx << ' ';
// }
// std::cout << '\n';
}
for (int i = 0 ; i < n ; ++i)
{
if (found[y[i]] == true)
{
continue;
}
if (before[y[i]] != 0)
{
candidates[y[i]].push_back(before[y[i]]);
}
int lastAdded = -1;
std::vector <int> added;
for (int j = 0 ; j < 2 && lastAdded + 1 < n ; ++j)
{
int curr = runBinaryY(lastAdded + 1, i);
if (curr != n)
{
candidates[y[i]].push_back(x[curr]);
}
lastAdded = curr;
}
if (candidates[y[i]].size() == 3)
{
if (Query({candidates[y[i]][0], candidates[y[i]][2], y[i]}) == 1)
{
std::swap(candidates[y[i]].back(), candidates[y[i]][1]);
} else if (Query({candidates[y[i]][1], candidates[y[i]][2], y[i]}) == 1)
{
std::swap(candidates[y[i]].back(), candidates[y[i]][0]);
}
candidates[y[i]].pop_back();
}
// std::cout << "candidates: " << y[i] << '\n';
// for (const int &idx : candidates[y[i]])
// {
// std::cout << idx << ' ';
// }
// std::cout << '\n';
}
// for (int i = 1 ; i <= 2 * n ; ++i)
// {
// if (candidates[i].size() == 3)
// {
// if (Query({candidates[i][0], candidates[i][2], i}) == 1)
// {
// std::swap(candidates[i].back(), candidates[i][1]);
// } else if (Query({candidates[i][1], candidates[i][2], i}) == 1)
// {
// std::swap(candidates[i].back(), candidates[i][0]);
// }
// candidates[i].pop_back();
// }
// }
std::iota(perm + 1, perm + 1 + 2 * n, 1);
std::sort(perm + 1, perm + 1 + 2 * n, [&](int x, int y)
{
return candidates[x].size() < candidates[y].size();
});
for (int idx = 1 ; idx <= 2 * n ; ++idx)
{
int i = perm[idx];
if (found[i])
{
continue;
}
if (candidates[i].size() == 1)
{
Answer(i, candidates[i][0]);
found[candidates[i][0]] = true;
// std::cout << "answer: " << i << ' ' << candidates[i][0] << '\n';
continue;
}
assert(candidates[i].size() == 2);
bool shouldBreak = false;
for (const int &j : candidates[i])
{
for (const int &x : candidates[j])
{
if (x == i)
{
// std::cout << "answer: " << i << ' ' << j << '\n';
Answer(i, j);
found[j] = true;
shouldBreak = true;
break;
}
}
if (shouldBreak)
{
break;
}
}
}
}
Compilation message
chameleon.cpp: In function 'int runBinaryX(int, int)':
chameleon.cpp:36:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (Query(curr) == curr.size()) l = mid;
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
chameleon.cpp: In function 'int runBinaryY(int, int)':
chameleon.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (Query(curr) == curr.size()) l = mid;
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
21 ms |
712 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
21 ms |
600 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
21 ms |
712 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
