#include <bits/stdc++.h>
void Solve(int N);
int Query(int x);
void Answer(int x, int y);
bool inMachine[100005];
int lastRes = 0;
int opCount = 0;
void setInMachine(int i, bool val) {
if (inMachine[i] != val) {
lastRes = Query(i);
opCount++;
inMachine[i] = val;
}
}
int query() {
return lastRes;
}
int ans[50000];
int maxAns[50000];
std::vector<int> a, b;
void Solve(int N) {
std::vector<int> order(2 * N);
std::iota(order.begin(), order.end(), 1);
std::mt19937 rng(time(NULL));
std::shuffle(order.begin(), order.end(), rng);
for (int i = 1; i <= 2 * N; i++) {
int prev = query();
setInMachine(i, true);
if (prev != query()) {
a.push_back(i);
} else {
maxAns[b.size()] = a.size() - 1;
b.push_back(i);
}
}
std::vector<bool> fixed(N);
int numSaved = 0;
int m = 1;
while (m < N) {
std::unordered_map<int, int> ansCounts;
for (int i = 0; i < N; i++) ansCounts[ans[i]]++;
std::unordered_map<int, int> numIncr, numSame;
std::unordered_set<int> fixed, fixedB;
for (int i = 0; i < N; i++) {
if (ans[i] + m > maxAns[i] || ansCounts[ans[i]] == 1) {
fixed.insert(ans[i]);
fixedB.insert(i);
numSame[ans[i]]++;
if (ansCounts[ans[i]] == 1) numSaved++;
}
}
std::vector<int> order(N);
std::iota(order.begin(), order.end(), 0);
std::shuffle(order.begin(), order.end(), rng);
std::vector<int> aSplitOne, aSplitTwo;
for (int i = 0; i < N; i++) {
if (fixed.find(i) == fixed.end()) {
if (i & m) {
aSplitTwo.push_back(i);
} else {
aSplitOne.push_back(i);
}
}
}
int costNormal = 0;
int costReverse = 0;
for (int x: aSplitOne) {
if (inMachine[a[x]]) {
costNormal++;
} else {
costReverse++;
}
}
for (int x: aSplitTwo) {
if (inMachine[a[x]]) {
costReverse++;
} else {
costNormal++;
}
}
/*std::cout << aSplitOne.size() << " " << aSplitTwo.size() << std::endl;
std::cout << costNormal << " " << costReverse << std::endl;
if (costNormal > costReverse) {
std::cout << "Losing " << costNormal - costReverse << " operations" << std::endl;
}*/
bool invert = costNormal > costReverse;
int numSet = 0;
std::vector<int> numSets;
opCount = 0;
for (int i = 0; i < N; i++) {
if (fixed.find(i) == fixed.end()) {
if (invert) {
setInMachine(a[i], !(i & m));
} else {
setInMachine(a[i], (i & m));
}
if ((i & m)) numSet++;
}
numSets.push_back(numSet);
}
//std::cout << opCount << " A " << costReverse << " " << costNormal << std::endl;
std::vector<double> probTrue;
double shift = 0.0;
for (int i = 0; i < N; i++) {
double prob = (numSets[maxAns[i]] - shift) / (double) (maxAns[i] + 1);
probTrue.push_back(prob);
shift += prob;
}
std::sort(order.begin(), order.end(), [&](int i, int j) {
return probTrue[i] > probTrue[j];
});
//std::cout << probTrue[order[0]] << std::endl;
for (int i: order) {
if (fixedB.find(i) != fixedB.end()) continue;
int totalStart = ansCounts[ans[i]];
int numChanged = numIncr[ans[i]];
int numStay = numSame[ans[i]];
int maxIncr = totalStart / 2;
int maxStay = totalStart - maxIncr;
bool incr;
if (numChanged == maxIncr) {
incr = false;
} else if (numStay == maxStay) {
incr = true;
} else if (ans[i] + m > maxAns[i]) {
incr = false;
} else {
int tmp = query();
setInMachine(b[i], !inMachine[b[i]]);
incr = query() == tmp;
if (invert) incr = !incr;
}
if (incr) {
numIncr[ans[i]]++;
ans[i] += m;
} else {
numSame[ans[i]]++;
}
}
m <<= 1;
}
for (int i = 0; i < N; i++) {
Answer(b[i], a[ans[i]]);
}
std::cout << numSaved << std::endl;
}
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <algorithm>
constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 1000000;
namespace {
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
int N;
int counterpart[2 * MAX_N + 1];
int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int count[2 * MAX_N + 1];
int num_answers;
int answer[2 * MAX_N + 1];
} // namespace
int Query(int x) {
if (!(1 <= x && x <= 2 * N)) {
printf("Query(%d)\n", x);
WrongAnswer(1);
}
if (++num_queries > MAX_CALLS) {
//WrongAnswer(2);
}
const int type = std::min(x, counterpart[x]);
if (on[x]) {
--on[x];
--count[type];
if (count[type] == 0) {
--num_kinds;
}
} else {
++on[x];
++count[type];
if (count[type] == 1) {
++num_kinds;
}
}
return num_kinds;
}
void Answer(int a, int b) {
if (N < 100)
std::cout << "Answer(" << a << ", " << b << ")" << std::endl;
if (++num_answers > N) {
WrongAnswer(6);
}
if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
WrongAnswer(3);
}
if (answer[a] != 0) {
WrongAnswer(4);
}
answer[a] = b;
if (answer[b] != 0) {
WrongAnswer(4);
}
answer[b] = a;
if (!(counterpart[a] == b && counterpart[b] == a)) {
WrongAnswer(5);
}
}
int secret_order[100000];
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for (int i = 0; i < 2 * N; ++i) {
secret_order[i] = i + 1;
}
std::mt19937 rng(0);
std::shuffle(secret_order, secret_order + 2 * N, rng);
for (int i = 1; i <= N; ++i) {
int x, y;
x = secret_order[2 * i - 2];
y = secret_order[2 * i - 1];
/*if (scanf("%d%d", &x, &y) != 2) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}*/
if (N < 100)
printf("%d %d\n", x, y);
counterpart[x] = y;
counterpart[y] = x;
}
Solve(N);
if (num_answers != N) {
WrongAnswer(6);
}
printf("Accepted: %d\n", num_queries);
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
