QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562416#7531. Hacking the Projectucup-team052#WA 654ms208688kbC++232.0kb2024-09-13 17:25:172024-09-13 17:25:17

Judging History

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

  • [2024-09-13 17:25:17]
  • 评测
  • 测评结果:WA
  • 用时:654ms
  • 内存:208688kb
  • [2024-09-13 17:25:17]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define D(...) fprintf(stderr,__VA_ARGS__)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int dp[27][1001][1001],ps[27][1001][1001];
int DP(int n,int rem,int low){
	//D("! %d %d %d\n",n,rem,low);
	if(n==1){
		return rem;
	}
	int &ret=dp[n][rem][low];
	if(ret!=-1)return ret;
	ret=rem+DP(n-1,rem-low,0);
	int pos=rem;
	rep(x,max(low+1,low==rem?0:ps[n][rem][low+1]-5),min(rem,low==rem?rem:ps[n][rem][low+1])){ // (low..x-1) (x..rem)
	//rep(x,low+1,rem){
		int pre=ret;
		ret=min(ret,max(DP(n-1,rem-low,0),DP(n,rem,x))+x);
		if(pre!=ret)pos=x;
	}
	//fprintf(stderr,"n=%d,rem=%d,low=%d,pos=%d\n",n,rem,low,pos);
	ps[n][rem][low]=pos;
	//if(low&&ps[n][rem][low]-ps[n][rem][low-1]>=20)fprintf(stderr,"n=%d,rem=%d,low=%d,pos=%d\n",n,rem,low,pos);
	return ret;
}
signed main(){
#ifdef xay5421
	//freopen("a.in","r",stdin);
#endif
	memset(dp,-1,sizeof(dp));
	// printf("%d\n",DP(26,200,0));
	rep(i,2,26){
		rep(rem,0,1000)per(low,rem,0)DP(i,rem,low);
	}
	//printf("%d\n",DP(26,1000,0));
	/*
	memset(dp,0x3f,sizeof(dp));
	rep(i,0,1000)dp[1][i][0]=i;
	rep(n,2,26){
		rep(rem,0,1000){
			rep(low,0,rem){
				int dp1 = dp[n - 1][rem - low][0];
			}
		}
	}
	*/
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		vector<string>ans;
		per(i,26,1){
			if(i==1){
				printf("query %c %d\n",i-1+'a',n);
				fflush(stdout);
				int x;
				scanf("%d",&x);
				rep(j,1,x){
					string s;
					cin>>s;
					ans.pb(s);
				}
			}else{
				int low=0;
				while(1){
					printf("query %c %d\n",i-1+'a',ps[i][n][low]);
					fflush(stdout);
					int x;
					scanf("%d",&x);
					if(x==n||x<ps[i][n][low]){
						rep(j,1,x){
							string s;
							cin>>s;
							ans.pb(s);
						}
						break;
					}else{
						low=x;
					}
				}
			}
		}
		sort(ans.begin(),ans.end());
		cout<<"answer ";
		for(auto&s:ans)cout<<s<<' ';
		cout<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 654ms
memory: 208688kb

input:

1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 cxyxy
2 cxyxy czzzz
0
2 aaa aba

output:

query z 1
query y 1
query x 1
query w 1
query v 1
query u 1
query t 1
query s 1
query r 1
query q 1
query p 1
query o 1
query n 1
query m 1
query l 1
query k 1
query j 1
query i 1
query h 1
query g 1
query f 1
query e 1
query d 1
query c 1
query c 3
query b 4
query a 4
answer cxyxy cxyxy czzzz 

result:

wrong answer Answer is wrong