QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397171#8553. Exchanging Kubic275307894aWA 31ms4000kbC++142.5kb2024-04-23 18:57:392024-04-23 18:57:39

Judging History

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

  • [2024-04-23 18:57:39]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:4000kb
  • [2024-04-23 18:57:39]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e3+5,M=1.5e8+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const ll INF=1e18+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n;ll A[N];
ll f[N][N];
ll qry(int x,int y){
	if(f[x][y]^-INF) return f[x][y];
	ll z;cout<<"? "<<x<<' '<<y<<endl;
	fflush(stdout);
	cin>>z;return f[x][y]=z;
}
int l[N],r[N],Bh;ll B[N];
void Solve(){
	int i,j;cin>>n;
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=-INF;
	for(i=1;i<=n;i++) A[i]=qry(i,i);
	for(i=1;i<=n&&!A[i];i++) A[i]=-1e15;
	for(i=n;i&&!A[i];i--) A[i]=-1e15;
	Bh=0;
	for(i=1;i<=n;i++){
		if(A[i]>0){
			if(B[Bh]) B[Bh]+=A[i],r[Bh]=i;
			else B[++Bh]=A[i],l[Bh]=r[Bh]=i;
		}
		else if(!A[i]){
			if(A[i-1]) B[++Bh]=0,l[Bh]=r[Bh]=i;
			else r[Bh]=i;
		}
	}
	for(i=1;i<=Bh;i++) gdb(l[i],r[i]);
	while(Bh>1){
		int flag=0;
		for(int i=2;i<=Bh;i+=2){
			if(qry(l[i-1],r[i+1])^max(B[i-1],B[i+1])){
				ll w=qry(l[i-1],r[i+1]);
				A[l[i]]=w-B[i-1]-B[i+1];
				r[i-1]=r[i+1];B[i-1]=w;
				rotate(B+i,B+i+2,B+Bh+1);rotate(l+i,l+i+2,l+Bh+1);rotate(r+i,r+i+2,r+Bh+1);
				Bh-=2;
				flag=1;break;
			}
		}
		gdb(flag);
		for(i=1;i<=Bh;i++) gdb(B[i],l[i],r[i]);
		if(flag) continue;
		if(Bh==3){A[l[2]]=-1e15;break;}
		int mi=3;for(int i=3;i+2<=Bh;i+=2) if(B[i]<B[mi]) mi=i;
		ll w=qry(l[mi-2],r[mi+2]);
		A[l[mi-1]]=-B[mi];A[l[mi+1]]=w-B[mi-2]-B[mi+2];
		r[mi-2]=r[mi+2];B[mi-2]=w;
		rotate(B+mi-1,B+mi+3,B+Bh+1);rotate(l+mi-1,l+mi+3,l+Bh+1);rotate(r+mi-1,r+mi+3,r+Bh+1);
		Bh-=4;
	}
	cout<<"! ";for(i=1;i<=n;i++) cout<<A[i]<<' ';cout<<endl;fflush(stdout);
}
int main(){
	// freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	int t=1;
	cin>>t;
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4000kb

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 -1000000000000000 1 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 1 3
? 1 5
! 2 -1 3 -1000000000000000 5 

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 31ms
memory: 3948kb

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
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! 938356223 
? 1 1
! 857157125 
? 1 1
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! -1000000000000000 
? 1 1
! 965894497 
? 1 1
! ...

result:

ok ok (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 3952kb

input:

1052
9
167536100
0
373372185
0
427949326
442758705
102715118
0
0
373372185
973423149
973423149

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 3 7
? 1 7
! 167536100 -373372185 373372185 -167536100 427949326 442758705 102715118 -1000000000000000 -1000000000000000 

result:

wrong answer mss of [1, 5] is incorrect, expected=427949326, found=633785411 (test case 1)