QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #324430 | #8230. Submissions | ucup-team1303# | WA | 107ms | 16364kb | C++14 | 2.8kb | 2024-02-10 18:56:50 | 2024-02-10 18:56:51 |
Judging History
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],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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16216kb
input:
2 5 TSxingxing10 G 0 rejected TSxingxing10 B 83 accepted aoliaoligeiliao J 98 accepted TS1 J 118 accepted TS1 B 263 accepted 12 AllWayTheNorth A 0 rejected YaoYaoLingXian Y 10 accepted XuejunXinyoudui1 X 200 rejected XuejunXinyoudui1 X 200 accepted LetItRot L 215 accepted AllWayTheNorth W 250 accept...
output:
2 TSxingxing10 TS1 4 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 16364kb
input:
2 2 jiangly_fan A 1 accepted jiangly B 23 accepted 3 conqueror_of_tourist A 1 accepted conqueror_of_tourist A 2 accepted tourist B 23 accepted
output:
2 jiangly_fan jiangly 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 16132kb
input:
2 13 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 rejected 12 A A 1 accepted A X 1 accepted B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 a...
output:
11 A K B C D E F G H I J 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 16216kb
input:
2 11 A A 1 accepted B B 1 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 accepted 12 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 a...
output:
2 A B 2 A K
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 107ms
memory: 16144kb
input:
100000 1 M3JytWoaEXxkACy_mBAQ R 111 accepted 1 sQ O 151 accepted 1 JinbrcS58gNEE5yTSkT B 140 accepted 1 cklwBY V 243 accepted 1 v_o42YmvEKFwy Q 260 rejected 1 ftQVK8S_um22w K 265 accepted 1 _bQBeFeDpYQhvZcLf9l3 Z 147 accepted 1 KvDcEAIDN A 75 rejected 1 H3MUK6 A 101 rejected 1 gxYo_oCFn2J8aIben U 54...
output:
1 M3JytWoaEXxkACy_mBAQ 1 sQ 1 JinbrcS58gNEE5yTSkT 1 cklwBY 1 v_o42YmvEKFwy 1 ftQVK8S_um22w 1 _bQBeFeDpYQhvZcLf9l3 1 KvDcEAIDN 1 H3MUK6 1 gxYo_oCFn2J8aIben 1 _isnlUGK0ddI 1 BERcVjyCp 1 6In2do_50ylch 1 f0r3SXc6brMjT 1 7njYOapSwvogA 1 x 1 y1w3KvxylfxwprRBYw 1 aGedzS 1 iPo0GDhIF 1 4Vf...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Wrong Answer
time: 45ms
memory: 16196kb
input:
10000 42 Bzs0PiQMXGZ5rRZ_2D G 2 accepted 9XtB_VIfbRRL E 11 accepted FVJL M 13 rejected a S 19 accepted tsd Z 20 rejected MyCqVEg1ONjZ U 22 accepted 6SgZMn N 51 rejected Qua1Pti3vKhyQKDUm P 54 accepted i29 M 63 accepted zPqu D 68 rejected xx2yiu6x C 71 rejected fYuK1KNkuyO5HRCq L 76 rejected tXWpYVqj...
output:
4 tsd Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 pVWDEz 3BQ 2 tg buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo wJlbqIU 9cy_y_RNRwex8j7224hz 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS _Yej1PrINtydmOudwo...
result:
wrong answer the numbers are different in the case 7272. (test case 7272)