| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 836308 | Liudas | Minerals (JOI19_minerals) | C++17 | 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 "minerals.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 2000000;
namespace {
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
int N;
int counterpart[2 * MAX_N + 1];
int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int countt[2 * MAX_N + 1];
int num_answers;
int answer[2 * MAX_N + 1];
} // namespace
int Query(int x) {
if (!(1 <= x && x <= 2 * N)) {
cout << x << endl;
WrongAnswer(1);
}
if (++num_queries > MAX_CALLS) {
WrongAnswer(2);
}
const int type = std::min(x, counterpart[x]);
if (on[x]) {
--on[x];
--countt[type];
if (countt[type] == 0) {
--num_kinds;
}
} else {
++on[x];
++countt[type];
if (countt[type] == 1) {
++num_kinds;
}
}
return num_kinds;
}
void Answer(int a, int b) {
if (++num_answers > N) {
WrongAnswer(6);
}
if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
WrongAnswer(3);
}
if (answer[a] != 0) {
WrongAnswer(4);
}
answer[a] = b;
if (answer[b] != 0) {
WrongAnswer(4);
}
answer[b] = a;
if (!(counterpart[a] == b && counterpart[b] == a)) {
WrongAnswer(5);
}
}
int last = 0;
void div(vector<int> start, vector<int> end, int par){
int N = start.size();
if(start.size() != end.size())
cout << start.size() << " " << end.size() << endl;
vector<int> l, r, le, re, left;
if(N == 1){
Answer(start[0], end[0]);
return;
}
if(par == 1){
for(int i = 0; i < N/2; i ++){
last = Query(start[i]);
l.push_back(start[i]);
}
for(int i = N/2; i < N; i ++){
r.push_back(start[i]);
}
for(int i = 0; i < N; i ++){
int t = Query(end[i]);
if(t != last){
last = t;
le.push_back(end[i]);
}
else{
re.push_back(end[i]);
}
}
div(le, l, 1);
div(r, re, 2);
}
else if (par == 2){
for(int i = 0; i < N/2; i ++){
last = Query(start[i]);
l.push_back(start[i]);
}
for(int i = N/2; i < N; i ++){
r.push_back(start[i]);
}
for(int i = 0; i < N; i ++){
int t = Query(end[i]);
if(t != last){
last = t;
le.push_back(end[i]);
}
else{
re.push_back(end[i]);
}
}
div(l, le, 0);
div(r, re, 1);
}
if(par == 0){
for(int i = 0; i < N/2; i ++){
last = Query(start[i]);
l.push_back(start[i]);
}
for(int i = N/2; i < N; i ++){
r.push_back(start[i]);
}
for(int i = 0; i < N; i ++){
int t = Query(end[i]);
if(t == last){
last = t;
le.push_back(end[i]);
if(le.size() == (N+1)/2){
for(int j = i + 1; j < N; j ++){
left.push_back(end[j]);
}
break;
}
}
else{
last = t;
re.push_back(end[i]);
if(le.size() == (N+1)/2){
for(int j = i + 1; j < N; j ++){
left.push_back(end[j]);
}
break;
}
}
}
if(!(re.size() + le.size() + left.size() == N)){
cout << re.size() << " " << left.size() << " " << le.size()<< " " << N << endl;
cout << "WTF" << endl;
}
//cout << re.size() << " " << left.size() << " " << le.size() << endl;
if(le.size() != N/2){
if(le.size() < (N+3)/4){
for(int i : le){
Query(i);
}
for(int i : left){
le.push_back(i);
}
div(l, le, 1);
}
else{
for(int i : left){
le.push_back(i);
Query(i);
}
div(l, le, 2);
}
}
else{
div(l, le, 2);
}
if(re.size() != N/2){
if(re.size() < (N + 3)/4){
for(int i : re){
Query(i);
}
for(int i : left){
re.push_back(i);
}
div(r, re, 0);
}
else{
for(int i : left){
re.push_back(i);
Query(i);
}
div(re, r, 1);
}
}
else{
div(re, r, 1);
}
}
}
void Solve(int N) {
vector<int> start, end;
vector<int> order(2 * N);
iota(order.begin(), order.end(), 0);
shuffle(order.begin(), order.end(), mt19937(225));
for(int i : order){
int t = start.size();
if(i < 0 || i >= N * 2){
cout << i << " ..." << endl;
}
int ans = Query(i+1);
if(ans == t + 1){
start.push_back(i+1);
}
else{
end.push_back(i+1);
}
}
last = N;
div(start, end, 2);
}