| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072641 | That_Salamander | Minerals (JOI19_minerals) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
void flip(int i) {
setInMachine(i, !inMachine[i]);
}
int query() {
return lastRes;
}
std::mt19937 rand(0);
void findMatching(std::vector<int>& a, std::vector<int>& b, bool aIsSet) {
if (a.size() == 0)
exit(1);
if (a.size() == 1) {
Answer(a[0], b[0]);
return;
}
std::shuffle(a.begin(), a.end(), rand);
std::shuffle(b.begin(), b.end(), rand);
std::vector<int> a1, a2, b1, b2;
int bound;
if (aIsSet) {
bound = (3 - sqrt(5)) / 2 * a.size();
} else {
bound = (1 - (3 - sqrt(5)) / 2) * a.size();
}
if (bound == 0) bound++;
if (bound == a.size()) bound--;
for (int i = 0; i < a.size(); i++) {
if (i < bound) {
a1.push_back(a[i]);
} else {
a2.push_back(a[i]);
}
}
//std::cout << a1.size() << " " << a2.size() << std::endl;
for (int x: a1) {
setInMachine(x, false);
}
for (int x: a2) {
setInMachine(x, true);
}
for (int x: b) {
if (a1.size() == b1.size()) b2.push_back(x);
else if (a2.size() == b2.size()) b1.push_back(x);
else {
int prev = query();
flip(x);
if (prev != query()) {
b1.push_back(x);
} else {
b2.push_back(x);
}
}
}
//std::cout << a1.size() << " " << b1.size() << std::endl;
findMatching(a1, b1, false);
findMatching(a2, b2, true);
}
void Solve(int N) {
lastRes = 0;
opCount = 0;
memset(inMachine, 0, sizeof(inMachine));
std::vector<int> a, b;
for (int i = 1; i <= 2 * N; i++) {
int prev = query();
flip(i);
if (prev == query()) {
b.push_back(i);
} else {
a.push_back(i);
}
}
findMatching(a, b, true);
}
#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::random_device rd;
std::mt19937 rng(rd());
int maxQueries = 0;
for (int iter = 0; iter < 100; iter++) {
num_queries = 0;
num_kinds = 0;
memset(on, 0, sizeof(on));
memset(count, 0, sizeof(count));
num_answers = 0;
memset(answer, 0, sizeof(answer));
memset(counterpart, 0, sizeof(counterpart));
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);
maxQueries = std::max(maxQueries, num_queries);
}
std::cout << "Max queries: " << maxQueries << std::endl;
return 0;
}
#endif