# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1226645 | ssafarov | Minerals (JOI19_minerals) | C++20 | 0 ms | 0 KiB |
int lst;
int op[100000] = {};
int ps[100000] = {};
void func(vector<int> v, bool ok){
// cout << lst << " " << ok << en;
// for(auto g : v) cout << g << " ";
// cout << en;
vector<int> v1, v2;
int st = lst;
int gps = v.size() / 2;
if(v.size() == 2){
Answer(v[0], v[1]);
return;
}
if(ok){
int sb = (gps + 1) / 2;
for(auto g : v){
int nw = lst;
if(op[g]){
if(sb){
v1.push_back(g);
sb--;
}else{
v2.push_back(g);
nw = Query(g);
ps[g] ^= 1;
}
}else{
nw = Query(g);
if(ps[g]){
if(nw == lst){
v1.push_back(g);
}else{
v2.push_back(g);
}
}else{
if(nw != lst){
v1.push_back(g);
}else{
v2.push_back(g);
}
}
ps[g] ^= 1;
}
lst = nw;
}
}else{
int sb = (gps + 1) / 2;
for(auto g : v){
int nw = lst;
if(op[g]){
if(sb){
v1.push_back(g);
sb--;
}else{
v2.push_back(g);
nw = Query(g);
ps[g] ^= 1;
}
}else{
nw = Query(g);
if(ps[v[0]]){
if(nw == lst){
v1.push_back(g);
}else{
v2.push_back(g);
}
}else{
if(nw != lst){
v1.push_back(g);
}else{
v2.push_back(g);
}
}
ps[g] ^= 1;
}
lst = nw;
}
}
func(v1, !ok);
func(v2, ok);
}
void Solve(int n){
for(int i = 1; i <= 2 * n; ++i){
int nw = Query(i);
ps[i] = 1;
if(nw != lst) op[i] = 1;
lst = nw;
}
vector<int> v;
for(int i = 1; i <= 2 * n; ++i){
v.push_back(i);
}
func(v, 1);
}