# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
203343 | theStaticMind | Minerals (JOI19_minerals) | C++14 | 443 ms | 6564 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>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define INF 1000000000//00000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
#include "minerals.h"
int last = 0;
set<int> S;
void add(int x){
if(S.count(x))S.erase(x);
else S.insert(x);
}
void extract(vector<int>& A, vector<int>& B, vector<int>& X, vector<int>& Y){
int n = sz(A), m = sz(B);
for(int i = 0; i < m; i++){
int v = Query(B[i]);
add(B[i]);
if(v == last){
X.pb(B[i]);
}
else Y.pb(B[i]);
last = v;
}
}
void divide(vector<int>& A, vector<int>& B){
int n = A.size();
if(n == 1){
Answer(A[0], B[0]);
return;
}
vector<int> X, Y;
vector<int> tempA, tempB;
for(int i = 0; i < n / 2; i++)tempA.pb(A[i]);
for(int i = n / 2; i < n; i++)tempB.pb(A[i]);
if(!(S.count(tempA[0]) ^ S.count(tempB[0]))){
if(tempB.size() > tempA.size()) swap(tempA, tempB);
for(int i = 0; i < tempB.size(); i++) last = Query(tempB[i]), add(tempB[i]);
}
if(S.count(tempB[0])){
swap(tempA, tempB);
}
extract(tempA, B, X, Y);
divide(tempA, X);
divide(tempB, Y);
}
void Solve(int N) {
vector<int> A, B;
vector<int> arr;
for(int i = 1; i <= 2 * N; i++)arr.pb(i);
srand(time(NULL));
for(int i = 0; i < 2 * N; i++) swap(arr[rand() % sz(arr)], arr[rand() % sz(arr)]);
for(auto i : arr){
int q;
if(last == N) q = last;
else q = Query(i);
S.insert(i);
if(last == q){
B.pb(i);
}
else{
A.pb(i);
}
last = q;
}
divide(A, B);
}
Compilation message (stderr)
# | 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... |