# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
489826 | Fran1024 | 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 "minerals.h"
#include <vector>
#include <set>
#include <stdio.h>
using namespace std;
set <int> stroj;
int MCNT = 0;
void ubaciniz(vector <int> &v) {
set <int> unizu;
for(int i = 0; i < v.size(); i++) {
unizu.insert(v[i]);
}
vector <int> pobrisani;
for(auto it = stroj.begin(); it != stroj.end(); it++) {
if(unizu.find(*it) == unizu.end()) {
Query(*it);
pobrisani.push_back(*it);
}
}
for(int i = 0; i < pobrisani.size(); i++) {
stroj.erase(pobrisani[i]);
}
for(int i = 0; i < v.size(); i++) {
if(stroj.find(v[i]) == stroj.end()) {
Query(v[i]);
stroj.insert(v[i]);
}
}
}
int ubaci(int x) {
if(stroj.find(x) == stroj.end()) {
stroj.insert(x);
return MCNT = Query(x);
}
return MCNT;
}
void izvadi(int x) {
if(stroj.find(x) != stroj.end()) {
stroj.erase(x);
MCNT = Query(x);
}
}
void divcon(vector <int> &a, vector <int> &b) {
if(a.size() == 1) {
Answer(a[0], b[0]);
return;
}
/*printf("a.size() = %d, b.size() = %d\n", a.size(), b.size());*/
vector <int> a1;
vector <int> b1;
vector <int> a2;
vector <int> b2;
for(int i = 0; i < a.size() / 2; i++) {
a1.push_back(a[i]);
}
for(int i = a.size() / 2; i < a.size(); i++) {
a2.push_back(a[i]);
}
ubaciniz(a1);
for(int i = 0; i < b.size(); i++) {
if(ubaci(b[i]) > a1.size()) {
b2.push_back(b[i]);
} else {
b1.push_back(b[i]);
}
}
divcon(a1, b1);
divcon(a2, b2);
}
void Solve(int N) {
vector <int> a;
vector <int> b;
for(int i = 1; i <= 2 * N; i++) {
ubaci(i);
if(MCNT == a.size()) {
izbaci(i);
b.push_back(i);
} else {
a.push_back(i);
}
}
//printf("a.size() = %d\n", a.size());
divcon(a, b);
}