| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 989148 | khanhphucscratch | 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<bits/stdc++.h>
#define int long long
#include "minerals.h"
using namespace std;
/*int Query(int x)
{
cout<<"? "<<x<<endl;
int ans; cin>>ans;
return ans;
}
void Answer(int a, int b)
{
cout<<"! "<<a<<" "<<b<<endl;
}*/
set<pair<int, int>> ans;
int dp[43001], place[43001], pre = 0;
bool state[43001];
int changeQuery(int32_t x)
{
state[x] ^= 1;
int cur = Query(x), a = cur - pre;
pre = cur;
return a;
}
void calculate(vector<int> a, vector<int> b, int ex, bool full)
{
if(a.size() == 1){
ans.insert({a[0], b[0]});
return;
}
int num = place[a.size()];
for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
/*cout<<"We're solving: "<<full<<" "<<ex<<endl;
for(int i : a) cout<<i<<" ";
cout<<endl;
for(int i : b) cout<<i<<" ";
cout<<endl;
cout<<"Optimal: "<<num<<endl;*/
vector<int> al, ar, bl, br;
for(int i = 0; i < num; i++){
al.push_back(a[i]);
if(ex < 0 || i > 0) changeQuery(a[i]);
}
for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
for(int i = 0; i < b.size()-1; i++){
if((changeQuery(b[i]) == 0) == full) br.push_back(b[i]);
else bl.push_back(b[i]);
}
int last = b[b.size()-1];
if(bl.size() == al.size()){
swap(bl, br); swap(al, ar); full ^= 1;
}
bl.push_back(last);
if(full == 0){ //left are 1
calculate(bl, al, last, (state[last]^1));
calculate(ar, br, -1, 0);
}
else{ //right are 1
calculate(bl, al, last, (state[last]^1));
calculate(ar, br, -1, 1);
}
}
void Solve(int n)
{
//Calculate dp
for(int i = 2; i <= n; i++){
dp[i] = 1e9;
for(int j = i/4; 2*j <= i; j++){ //pray
int val = i+j-1+dp[j]+dp[i-j];
if(val < dp[i]){dp[i] = val; place[i] = j;}
}
}
vector<int> a, b;
for(int i = 1; i <= 2*n; i++){
if(changeQuery(i) == 1) a.push_back(i);
else b.push_back(i);
}
calculate(a, b, -1, 1);
for(pair<int, int> i : ans) Answer(i.first, i.second);
}