QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#562400#7531. Hacking the Projectucup-team052#TL 0ms0kbC++232.0kb2024-09-13 17:20:532024-09-13 17:20:54

Judging History

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

  • [2024-09-13 17:20:54]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-13 17:20:53]
  • 提交

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',dp[i][n][low]);
					fflush(stdout);
					int x;
					scanf("%d",&x);
					if(x<dp[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;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

1
4

output:

query z 34

result: