QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544880#8553. Exchanging KubicRykonyWA 1ms3588kbC++202.0kb2024-09-02 20:45:012024-09-02 20:45:02

Judging History

This is the latest submission verdict.

  • [2024-09-02 20:45:02]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3588kb
  • [2024-09-02 20:45:01]
  • Submitted

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)