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>
using namespace std;
// #define __LOCAL__
#ifdef __LOCAL__
void Solve(int N);
const int SIZE = 1e3 + 5;
int type[SIZE], cnt[SIZE], in_cnt[SIZE];
int ttl = 0, qcnt = 0;
int Query(int i){
qcnt++;
if(!cnt[type[i]])
ttl++;
if(in_cnt[i]){
cnt[type[i]]--;
in_cnt[i] = 0;
}
else if(!in_cnt[i]){
cnt[type[i]]++;
in_cnt[i] = 1;
}
if(!cnt[type[i]])
ttl--;
return ttl;
}
void Answer(int a, int b){
if(type[a] != type[b])
cout << a << ' ' << b << " WA\n";
}
int main(){
int n;
cin >> n;
for (int i = 1, a, b; i <= n;i++){
cin >> a >> b;
type[a] = i;
type[b] = i;
}
Solve(n);
cout << qcnt << '\n';
}
#endif
#ifndef __LOCAL__
#include "minerals.h"
#endif
#define uwu return;
const double magic = exp(-1);
void solve(vector<int> A, vector<int> B, bool b){
if(A.empty())
uwu
if(A.size() == 1){
Answer(A[0], B[0]);
uwu
}
int m = max((int) (b * A.size() + (1 - b * 2) * magic * A.size()), 1);
vector<int> recA[2], recB[2];
for (int i = 0; i < A.size(); i++){
recA[i >= m].push_back(A[i]);
}
int prev;
for(auto i : recA[b]){
prev = Query(i);
}
for(auto i : B){
if(recA[0].size() == recB[0].size()){
recB[1].push_back(i);
}
else if(recA[1].size() == recB[1].size()){
recB[0].push_back(i);
}
else{
int now = Query(i);
now == prev ? recB[0].push_back(i) : recB[1].push_back(i);
prev = now;
}
}
solve(recA[0], recB[0], 1), solve(recA[1], recB[1], 0);
return;
}
void Solve(int N){
vector<int> veca, vecb;
for (int i = 1, pre = 0, tmp = 0; i <= 2 * N; i++){
tmp = Query(i);
if(tmp == pre)
veca.push_back(i);
else
vecb.push_back(i);
pre = tmp;
}
random_shuffle(veca.begin(), veca.end());
random_shuffle(vecb.begin(), vecb.end());
solve(veca, vecb, 1);
uwu
}
Compilation message (stderr)
minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < A.size(); i++){
| ~~^~~~~~~~~~
minerals.cpp:90:25: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
90 | now == prev ? recB[0].push_back(i) : recB[1].push_back(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... |