QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544816#8553. Exchanging KubicRykonyWA 25ms3612kbC++202.2kb2024-09-02 20:23:482024-09-02 20:23:48

Judging History

你现在查看的是最新测评结果

  • [2024-09-02 20:23:48]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:3612kb
  • [2024-09-02 20:23:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
#define INF 1e15

struct node{
    int l;
    int r;
    LL sum;
    node(){}
    node(int _l,int _r,LL _sum){
        l=_l;
        r=_r;
        sum=_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(node(a[l].l,a[i-1].r,sum));
	                    tp=0;
	                    l=i;
	                }
	                sum=0;
	            }
	            else{
					if (!tp){
						z.push_back(node(a[l].l,a[i-1].r,sum));
						tp=a[i].sum;
						l=i;
					}
					sum+=a[i].sum;
				}
	        }
	        z.push_back(node(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);
//        	cout<<"----------\n";
//        	for (auto p:z){
//				cout<<p.l<<" "<<p.r<<" "<<p.sum<<'\n';
//			}
//			cout<<"----------\n";
        	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;
				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: 100
Accepted
time: 1ms
memory: 3588kb

input:

2
3
1
0
1
1
5
2
0
3
0
5
4
5
5

output:

? 1 1
? 2 2
? 3 3
? 1 3
! 1 -1000000000000000 1 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 1 3
? 1 5
? 1 5
! 2 -1 3 -1000000000000000 5 

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 25ms
memory: 3520kb

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...

result:

ok ok (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3612kb

input:

1052
9
167536100
0
373372185
0
427949326
442758705
102715118
0
0
373372185
973423149
9
248442934
306962195
570791475
593033322
0
582850731
559429390
0
120053133
2780526396
2780526396
2780526396
10
785691778
0
981032824
0
0
592503870
0
0
0
0
981032824
1112480382
1112480382
10
0
737563509
985502704
42...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 3 7
! 167536100 -1000000000000000 373372185 -1000000000000000 427949326 442758705 102715118 -1000000000000000 0 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 7
? 1 9
? 1 9
! 248442934 306962195 570791475 593033322 -80983651 5...

result:

wrong answer mss of [1, 8] is incorrect, expected=1487295068, found=1412327335 (test case 7)