#include<bits/stdc++.h>
#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;
long long dp[43001], place[43001], pre = 0;
bool state[43001];
int changeQuery(int 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] = 1e18;
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<int>, std::vector<int>, int, bool)':
minerals.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < a.size(); i++) if(a[i] == ex){swap(a[i], a[0]); break;}
| ~~^~~~~~~~~~
minerals.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = num; i < a.size(); i++) ar.push_back(a[i]);
| ~~^~~~~~~~~~
minerals.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < b.size()-1; i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
