QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562418 | #7531. Hacking the Project | ucup-team052# | WA | 579ms | 207512kb | C++23 | 2.0kb | 2024-09-13 17:27:22 | 2024-09-13 17:27:22 |
Judging History
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);
}
n-=x;
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: 579ms
memory: 207512kb
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 1 aaa
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 3 query a 1 answer cxyxy cxyxy czzzz
result:
wrong answer Answer is wrong