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 "minerals.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
bool chk[100009];
int query(int x) {
chk[x] = !chk[x];
//printf("query x: %d\n", x);
return Query(x);
}
void answer(int a, int b) {
//printf("answer: (%d, %d)\n", a, b);
Answer(a, b);
}
pair<vi, vi> split(int N) {
vector<int> A, B;
int pr = 0, i = 0;
for(i=1; i<=2*N; i++) {
int Q = query(i);
if(pr != Q) A.push_back(i);
else B.push_back(i);
pr = Q;
}
return {A, B};
}
void go(vector<int> &A, vector<int> &B, bool AC) {
//puts("AB");
//for(auto& it: A) printf("%d ",it); puts("");
//for(auto& it: B) printf("%d ",it); puts("");
int N = A.size();
if(N == 1) {
answer(A[0], B[0]);
return;
}
vector<int> LA, RA, LB, RB;
int m = N/2, pr;
if(!AC) {
if(N >= 10) m = N - (int)(1.0*N/1.618);
for(int i=0; i<m; i++) {
pr = query(A[i]);
LA.push_back(A[i]);
}
for(int i=m; i<N; i++) RA.push_back(A[i]);
}
if(AC) {
if(N >= 10) m = (int)(1.0*N/1.618);
for(int i=N-1; i>=m; i--) {
pr = query(A[i]);
RA.push_back(A[i]);
}
for(int i=0; i<m; i++) LA.push_back(A[i]);
}
int i;
for(i=0; i<N; i++) {
int Q = query(B[i]);
if(pr != Q) RB.push_back(B[i]);
else LB.push_back(B[i]);
if(RB.size() == RA.size()) break;
if(LB.size() == LA.size()) break;
pr = Q;
}
if(RB.size() == RA.size()) for(++i; i<N; i++) LB.push_back(B[i]);
else for(++i; i<N; i++) RB.push_back(B[i]);
go(LA, LB, 1);
go(RA, RB, 0);
}
void Solve(int N) {
vi A, B; tie(A, B) = split(N);
go(A, B, 1);
}
Compilation message (stderr)
minerals.cpp: In function 'void go(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:61:9: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(pr != Q) RB.push_back(B[i]);
^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |