QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #623 | #325718 | #8230. Submissions | ushg8877 | grass8cow | Success! | 2024-05-20 23:50:41 | 2024-05-20 23:50:42 |
Details
Extra Test:
Wrong Answer
time: 3ms
memory: 36568kb
input:
1 25 T G 14 accepted K F 23 accepted F K 25 rejected T H 28 accepted A K 38 rejected K F 38 accepted P D 43 accepted D J 44 accepted E Q 47 accepted K B 58 rejected L B 62 rejected F Q 62 accepted M S 63 accepted M C 64 rejected H Y 65 accepted O C 67 accepted U W 72 rejected S L 72 accepted X U 77 ...
output:
6 T K F M O C
result:
wrong answer the numbers are different in the case 1. (test case 1)
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #325718 | #8230. Submissions | grass8cow | WA | 137ms | 85224kb | C++17 | 2.8kb | 2024-02-11 20:33:49 | 2024-05-20 23:51:12 |
answer
#include<bits/stdc++.h>
using namespace std;
const int I=2e8+10;
int q,n,fs[401000][26],fs2[401000][26],fe[401000][26],fi[401000][26],lst[401000],bb[401000];
string ie[401000];
map<string,int>o;
#define ll long long
ll qc[401000];int cn,s1[401000],V1[200100],V2[201000],s2[401000],s3[401000],s4[401000];
bool ans[401000];
ll bp(ll x,ll y){return x*(I+1)-y;}
void sol(){
o.clear();
cin>>q;n=0;
for(int i=1;i<=q;i++){
string s;cin>>s;
if(!o[s]){
o[s]=++n,ie[n]=s;
lst[n]=-1,bb[n]=0;
for(int j=0;j<26;j++)fs[n][j]=fe[n][j]=fs2[n][j]=0,fi[n][j]=-1;
}
int u=o[s];
cin>>s;int t=s[0]-'A',ti;cin>>ti>>s;
lst[u]=ti,bb[u]++;
if(fe[u][t]>=2)continue;
if(fi[u][t]==-1)fi[u][t]=ti;
if(s[0]=='a'){
if(!fe[u][t])fe[u][t]=1,fs2[u][t]=fs[u][t]+20,fs[u][t]+=ti;
else fe[u][t]=2,fs2[u][t]+=ti;
}
else{
if(!fe[u][t])fs[u][t]+=20;
else fs2[u][t]+=20;
}
}
//case1:让别人变软
cn=0;
int n_=0;
for(int i=1;i<=n;i++){
ans[i]=0;
int v1=0,v2=0;
for(int j=0;j<26;j++)if(fe[i][j])v1++,v2+=fs[i][j];
V1[i]=v1,V2[i]=v2;
qc[++cn]=bp(v1,v2);
n_+=(v1>0);
}
sort(qc+1,qc+cn+1);cn=unique(qc+1,qc+cn+1)-qc-1;
for(int i=1;i<=cn;i++)s1[i]=s2[i]=s3[i]=0;
//case1:别人变软
int Z=cn+1;
for(int i=1;i<=n;i++){
int v1=V1[i],v2=V2[i],mi=I,mx2=-I;
if(!v1)Z=min(Z,(int)(lower_bound(qc+1,qc+cn+1,bp(1,lst[i]+20*(bb[i]-1)))-qc));
if(!v1)continue;
for(int j=0;j<26;j++)if(fe[i][j]){
if(fe[i][j]==1)mi=min(mi,fs[i][j]);
else mx2=max(mx2,-fs[i][j]+fs2[i][j]);
}
int L=lower_bound(qc+1,qc+cn+1,(mi!=I)?bp(v1-1,v2-mi):bp(v1,v2+mx2))-qc,R=lower_bound(qc+1,qc+cn+1,bp(v1,v2))-qc;
if(v1==1)s1[L]++,s1[R]--;
else s2[L]++,s2[R]--;
s3[R]++;
}
s3[cn+1]=0;
//极特殊情况：让0题队过题，使得n_变大
for(int i=cn;i;i--)s3[i]+=s3[i+1];
for(int i=1;i<=cn;i++)s1[i]+=s1[i-1],s2[i]+=s2[i-1];
for(int i=1;i<=n;i++){
int v1=V1[i],v2=V2[i],R=lower_bound(qc+1,qc+cn+1,bp(v1,v2))-qc;
if(s3[R+1]<min(35,(n_+9)/10))ans[i]=1;
if(s2[R]&&s3[R+1]-1<min(35,(n_+9)/10))ans[i]=1;
if(s1[R]&&s3[R+1]-1<min(35,(n_+8)/10))ans[i]=1;
if(R>=Z&&s3[R+1]<min(35,(n_+10)/10))ans[i]=1;
}
//case2:自己变硬
for(int i=1;i<=n;i++){
int v1=V1[i],v2=V2[i],mi1=I,mi2=I;
for(int j=0;j<26;j++)if(fi[i][j]!=-1){
if(!fe[i][j])mi1=min(mi1,fi[i][j]);
else mi2=min(mi2,fi[i][j]-fs[i][j]);
}
if(mi1==I&&mi2==I)continue;
int R=upper_bound(qc+1,qc+cn+1,(mi1!=I)?bp(v1+1,v2+mi1):bp(v1,v2+mi2))-qc;
if(s3[R]<min(35,(n_+9+(v1==0))/10))ans[i]=1;
}
int gg=0;
for(int i=1;i<=n;i++)if(ans[i])gg++;
cout<<gg<<endl;
for(int i=1;i<=n;i++)if(ans[i])cout<<ie[i]<<" ";
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;while(T--)sol();
return 0;
}