QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#393806 | #8553. Exchanging Kubic | YMH_fourteen | WA | 17ms | 3888kb | C++14 | 2.2kb | 2024-04-19 13:06:56 | 2024-04-19 13:06:56 |
Judging History
answer
// Author: Minghan Ye (Donotplaygame)
// Name: L. Exchanging Kubic
// URL: https://qoj.ac/contest/1596/problem/8553
// ML: 1024 MB
// TL: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "E:/OI/normal/templates/debug.h"
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define fi first
#define se second
const int N=2005;
int n;
ll a[N],sm[N];
ll ask(int l,int r)
{
cout<<"? "<<l<<" "<<r<<endl;
ll res;cin>>res;
return res;
}
void answer()
{
cout<<"!";
for(int i=1;i<=n;i++)cout<<" "<<a[i];
cout<<endl;
}
void upd()
{
for(int i=1;i<=n;i++)sm[i]=sm[i-1]+a[i];
}
ll sum(int l,int r){return sm[r]-sm[l-1];}
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr);
int _;cin>>_;while(_--)
{
cin>>n;
for(int i=1;i<=n;i++)a[i]=ask(i,i);
vector<PII> p;
for(int i=1,lst=0;i<=n+1;i++)
if(a[i]>0)
{
if(!lst)lst=i;
}
else
{
if(lst)p.PB(lst,i-1);
lst=0;
}
while(p.size()>1)
{
// cerr<<"p = [";
// for(int i=0;i<p.size();i++)fprintf(stderr,"(%d, %d)%s",p[i].fi,p[i].se,i+1==p.size()?"]\n":", ");
upd();
vector<PII>::iterator it;
for(auto i=p.begin();i!=p.end();i++)
if(i==p.begin()||sum(i->fi,i->se)<sum(it->fi,it->se))it=i;
if(it!=p.begin())
{
ll t=ask((it-1)->fi,it->se),s=sum((it-1)->fi,(it-1)->se),u=s+sum(it->fi,it->se);
if(t>s)
{
a[it->fi-1]=t-u;
for(int i=(it-1)->se+1;i<it->fi-1;i++)a[it->fi-1]-=a[i];
int st=(it-1)->fi,ed=it->se;
p.emplace(p.erase(it-1,it+1),st,ed);
continue;
}
}
if(it+1!=p.end())
{
ll t=ask(it->fi,(it+1)->se),s=sum((it+1)->fi,(it+1)->se),u=s+sum(it->fi,it->se);
if(t>s)
{
a[it->se+1]=t-u;
for(int i=it->se+2;i<(it+1)->fi;i++)a[it->se+1]-=a[i];
int st=it->fi,ed=(it+1)->se;
p.emplace(p.erase(it,it+2),st,ed);
continue;
}
}
a[it->fi-1]=a[it->se+1]=-sum(it->fi,it->se);
p.erase(it);
}
answer();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
2 3 1 0 1 1 5 2 0 3 0 5 4 5
output:
? 1 1 ? 2 2 ? 3 3 ? 1 3 ! 1 -1 1 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 1 3 ? 1 5 ! 2 -1 3 -4 5
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 17ms
memory: 3592kb
input:
10000 1 718876398 1 0 1 0 1 0 1 938356223 1 857157125 1 0 1 0 1 0 1 0 1 0 1 965894497 1 0 1 626061677 1 642094813 1 107398046 1 0 1 0 1 0 1 287188651 1 0 1 345108193 1 0 1 0 1 714952783 1 0 1 325760098 1 0 1 800487422 1 322806679 1 0 1 0 1 0 1 866952779 1 741483102 1 492063609 1 0 1 833448280 1 0 1 ...
output:
? 1 1 ! 718876398 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 938356223 ? 1 1 ! 857157125 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 965894497 ? 1 1 ! 0 ? 1 1 ! 626061677 ? 1 1 ! 642094813 ? 1 1 ! 107398046 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 287188651 ? 1 1 ! 0 ? 1 1 ! 345108193 ? 1 1 ! ...
result:
ok ok (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3688kb
input:
1052 9 167536100 0 373372185 0 427949326 442758705 102715118 0 0 373372185 973423149 9 248442934 306962195 570791475 593033322 0 582850731 559429390 0 120053133 1142280121 2780526396 10 785691778 0 981032824 0 0 592503870 0 0 0 0 1112480382 1112480382 10 0 737563509 985502704 427600980 0 805973591 7...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 1 3 ? 3 7 ! 167536100 -373372185 373372185 -373372185 427949326 442758705 102715118 0 0 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 6 9 ? 1 7 ! 248442934 306962195 570791475 593033322 -80983651 582850731 559429390 -120053133 1200531...
result:
wrong answer mss of [1, 9] is incorrect, expected=2230789165, found=2782549324 (test case 10)