#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);
}
Compilation message
minerals.cpp: In function 'void calculate(std::vector<long long int>, std::vector<long long int>, long long int, bool)':
minerals.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
| ~~^~~~~~~~~~
minerals.cpp:44:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
| ~~^~~~~~~~~~
minerals.cpp:45:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < b.size()-1; i++){
| ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccqsE7id.o: in function `changeQuery(int)':
minerals.cpp:(.text+0x17): undefined reference to `Query(long long)'
/usr/bin/ld: /tmp/ccqsE7id.o: in function `calculate(std::vector<long long, std::allocator<long long> >, std::vector<long long, std::allocator<long long> >, long long, bool)':
minerals.cpp:(.text+0x229): undefined reference to `Query(long long)'
/usr/bin/ld: minerals.cpp:(.text+0x38a): undefined reference to `Query(long long)'
/usr/bin/ld: /tmp/ccqsE7id.o: in function `Solve(long long)':
minerals.cpp:(.text+0xfb1): undefined reference to `Query(long long)'
/usr/bin/ld: minerals.cpp:(.text+0x11ab): undefined reference to `Answer(long long, long long)'
/usr/bin/ld: /tmp/ccPIScNa.o: in function `main':
grader.cpp:(.text.startup+0xbd): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status
