QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544880 | #8553. Exchanging Kubic | Rykony | WA | 1ms | 3588kb | C++20 | 2.0kb | 2024-09-02 20:45:01 | 2024-09-02 20:45:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 1e15
struct node{
int l;
int r;
LL sum;
};
int main()
{
int _=1;
cin>>_;
while (_--){
int n;
cin>>n;
vector <node> a;
vector <LL> ans(n+10,0);
LL x;
for (int i=1;i<=n;i++){
cout<<"? "<<i<<" "<<i<<'\n';
cin>>x;
a.push_back({i,i,x});
ans[i]=x;
}
auto nor=[&](vector <node> a)
{
int l=0,tp=a[0].sum;
LL sum=0;
vector <node> z;
for (int i=0;i<(int)a.size();i++){
if (!a[i].sum){
if (tp){
z.push_back({a[l].l,a[i-1].r,sum});
tp=0;
l=i;
}
sum=0;
}
else{
if (!tp){
z.push_back({a[l].l,a[i-1].r,sum});
tp=a[i].sum;
l=i;
}
sum+=a[i].sum;
}
}
z.push_back({a[l].l,a[a.size()-1].r,sum});
return z;
};
vector <node> z;
LL mss=0,res;
while (1){
int cnt=0;
z=nor(a);
a.clear();
int zp=0;
for (int i=0;i<(int)z.size()-2;i++){
if (i&&!z[i].sum&&!zp) a.push_back(z[i]);
if (!z[i].sum) continue;
if (z[i].sum&&z[i+2].sum&&!z[i+1].sum) cout<<"NOOOOO"<<'\n';
mss=max(z[i].sum,z[i+2].sum);
cout<<"? "<<z[i].l<<" "<<z[i+2].r<<'\n';
cin>>res;
if (res>=mss){
ans[z[i+1].l]=-z[i].sum-z[i+2].sum+res;
z[i+2]={z[i].l,z[i+2].r,res};
cnt++;
zp=1;
}
else a.push_back(z[i]),zp=0;
}
int f=z.size()-1;
if (z[f-1].sum) a.push_back(z[f-1]);
else if (!zp) a.push_back(z[f-1]),a.push_back(z[f]);
else a.push_back(z[f]);
if (!cnt) break;
}
cout<<"! ";
for (int i=1;i<=n;i++){
if (ans[i-1]>0&&!ans[i]) ans[i]=-INF;
cout<<ans[i]<<" ";
}
cout<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3588kb
input:
2 3 1 0 1
output:
? 1 1 ? 2 2 ? 3 3 NOOOOO ? 1 3
result:
wrong answer You should either "?" or "!". (test case 1)