QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344612 | #8230. Submissions | zzuqy | WA | 115ms | 17240kb | C++14 | 5.5kb | 2024-03-04 20:25:08 | 2024-03-04 20:25:09 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200009
using namespace std;
int a[N][26][4];//0 now;1 highest;2 lowest
unordered_map<string,int>mp;
string rmp[N];
int n,n2;
bool cmp(const pair<int,int> &a,const pair<int,int>&b){
if(a.first>b.first)return 1;
if(a.first<b.first)return 0;
if(a.second<b.second)return 1;
return 0;
}
struct mapstruct{
bool operator()(const pair<int,int> &a,const pair<int,int>&b){
return cmp(a,b);
}
};
int calcgold(int n){
return min((n+9)/10,35);
}
bool in[N];
int goldsize=0;
map<pair<int,int>,int,mapstruct>gold;
vector<int>gold2[N];
pair<int,int>line;
void handle(){
int x=calcgold(n2);
int cnt=0;
//assert(gold.size()<=x+1);
for(auto i:gold){
if(cnt<x)for(auto j:gold2[i.second])in[j]=1,cnt++;
else break;
//cout<<cnt<<"?"<<x<<endl;
}
}
void del(int x,pair<int,int>score){
if(score.first>0)n2--;
if(!cmp(line,score)){
int id=gold[score];
for(int i=0;i<gold2[id].size();i++){
if(gold2[id][i]==x){
swap(gold2[id][i],gold2[id][gold2[id].size()-1]);
gold2[id].pop_back();
break;
}
}
if(gold2[id].size()==0)gold.erase(score);
}
}
void add(int x,pair<int,int>score){
if(score.first>0)n2++;
//cout<<score.first<<" "<<score.second<<endl;
if(!cmp(line,score)){
if(gold[score]==0){
gold[score]=++goldsize;
gold2[goldsize].clear();
}
gold2[gold[score]].push_back(x);
}
}
void query(int x,pair<int,int>normal,pair<int,int>score){
del(x,normal);
add(x,score);
handle();
del(x,score);
add(x,normal);
}
void solve(){
mp.clear();n=n2=0;line=make_pair(0,0);
gold.clear();goldsize=0;
int m;cin>>m;
while(m--){
string s;char c;int t;string p;
cin>>s>>c>>t>>p;
if(mp[s]==0){
mp[s]=++n;rmp[n]=s;
for(int i=0;i<26;i++)a[n][i][0]=a[n][i][1]=a[n][i][2]=-1000000000;
}
int x=mp[s],id=c-'A';
if(p=="accepted"){
if(a[x][id][0]<0)a[x][id][0]=a[x][id][0]+1000000000+t,a[x][id][2]+=20;
else a[x][id][2]=a[x][id][2]+1000000000+t;
//cout<<x<<" "<<id<<" "<<a[x][id][2]<<endl;
if(a[x][id][1]<0)a[x][id][1]=t;
}
if(p=="rejected"){
if(a[x][id][0]<0)a[x][id][0]+=20,a[x][id][3]=t;
if(a[x][id][1]<0)a[x][id][1]=t;
if(a[x][id][2]<0)a[x][id][2]+=20;
}
}
for(int i=1;i<=n;i++){
int c=0,p=0;
for(int j=0;j<26;j++)if(a[i][j][0]>=0)c++,p+=a[i][j][0];
if(gold[make_pair(c,p)]==0){
gold[make_pair(c,p)]=++goldsize;
gold2[goldsize].clear();
}
gold2[gold[make_pair(c,p)]].push_back(i);
if(c>0)n2++;
//cout<<rmp[i]<<" "<<c<<" "<<p<<endl;
}
int cnt=0;
for(auto it:gold){
line=it.first;
cnt+=gold2[it.second].size();
if(cnt>calcgold(n2))break;
}
while(1){
auto it=gold.end();it--;
if(cmp(line,(*it).first))gold.erase(it);
else break;
}
handle();
for(int i=1;i<=n;i++){
pair<int,int>best=make_pair(-1000,0),worst=make_pair(1000,0),normal=make_pair(0,0);
for(int x=0;x<26;x++)if(a[i][x][0]>=0)normal.first++,normal.second+=a[i][x][0];
int c=0,p=0;
for(int x=0;x<26;x++){
c=0;p=0;
if(a[i][x][0]>=0)c--,p-=a[i][x][0];
if(a[i][x][1]>=0)c++,p+=a[i][x][1];
if(cmp(make_pair(c,p),best))best=make_pair(c,p);
}
best.first+=normal.first;best.second+=normal.second;
for(int x=0;x<26;x++){
c=0;p=0;
if(a[i][x][0]>=0)c--,p-=a[i][x][0];
if(a[i][x][2]>=0)c++,p+=a[i][x][2];
if(cmp(worst,make_pair(c,p)))worst=make_pair(c,p);
}
worst.first+=normal.first;worst.second+=normal.second;
pair<int,int>what=make_pair(0,0);
for(int x=0;x<26;x++){
if(a[i][x][0]<0&&a[i][x][0]>-1000000000)what.second=max(what.second,a[i][x][0]-20+1000000000+a[i][x][3]+1);
}
//cout<<normal.first<<"-"<<normal.second<<" ";
//cout<<best.first<<"-"<<best.second<<" ";
//cout<<worst.first<<"-"<<worst.second<<" ";
if(normal!=best){
if(cmp(best,line)||normal.first==0&&n2%10==0)query(i,normal,best);
}
if(normal!=worst&&!cmp(line,normal))query(i,normal,worst);
if(normal.first==0&&what.second){
what.first++;what.second--;
//cout<<what.first<<"-"<<what.second<<" ";
query(i,normal,what);
}
//cout<<endl;
}
int ans=0;
for(int i=1;i<=n;i++)if(in[i])ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++)if(in[i])cout<<rmp[i]<<" ";cout<<endl;
for(int i=1;i<=n;i++){
rmp[i]="";in[i]=0;
for(int j=0;j<26;j++)a[i][j][0]=a[i][j][1]=a[i][j][2]=0;
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
int t;cin>>t;
while(t--)solve();
return 0;
}
/*
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 accepted
ImYourFan I 257 accepted
ImYourFan Y 257 accepted
AllWayTheNorth T 264 accepted
XuejunXinyoudui1 J 294 accepted
LetItRot I 299 accepted
LetItRot I 299 rejected
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
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 1 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 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 rejected
K K 2 rejected
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14800kb
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: 2ms
memory: 16620kb
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: 4ms
memory: 15412kb
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: 14888kb
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: 115ms
memory: 15292kb
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: 0
Accepted
time: 52ms
memory: 15520kb
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:
ok 10000 test cases ok. (10000 test cases)
Test #7:
score: 0
Accepted
time: 39ms
memory: 15996kb
input:
10000 27 bhAGFVDBjp4_Tvo U 24 accepted bhAGFVDBjp4_Tvo O 37 rejected bhAGFVDBjp4_Tvo D 40 accepted bhAGFVDBjp4_Tvo H 45 accepted bhAGFVDBjp4_Tvo B 60 rejected bhAGFVDBjp4_Tvo J 63 accepted bhAGFVDBjp4_Tvo M 81 rejected bhAGFVDBjp4_Tvo M 98 rejected bhAGFVDBjp4_Tvo D 103 rejected bhAGFVDBjp4_Tvo Q 11...
output:
1 bhAGFVDBjp4_Tvo 2 euenQ rl 1 seny 2 nLWe5xvBqfYkN 8zfFqdixKjh 1 VDeEtfbb 1 9PAd7wtbCZMws6u 1 Wsfc5qold4uacAjI1y 2 NX6GLK3Nz h68cyLwQ7drM__pSJub 3 yOgwg U7S8zgJhR6 sdf0IGct21OeEFJ 1 acesvM9yT 1 2hQb 2 3twK2MJI_ P5 1 eGCz 3 39GgHUPovILESCd0 tLHWIEVr5i7vlKpvlP UXRu8i 1 20gsbZ25SsYp8 1 ...
result:
ok 10000 test cases ok. (10000 test cases)
Test #8:
score: 0
Accepted
time: 44ms
memory: 15120kb
input:
10000 2 vVflLovvnhJEO U 3 accepted Fg P 48 rejected 12 V9UJ5hEaWiwMq3lxwKw9 P 30 accepted CKsw M 34 rejected dCZBzKMxgQfgBDZO R 50 rejected A1R2kF N 54 rejected A1R2kF X 65 accepted HEih51ut H 68 rejected HEih51ut J 75 rejected l0MCFXNXlH6T2wT I 163 accepted A1R2kF B 180 accepted dCZBzKMxgQfgBDZO A ...
output:
1 vVflLovvnhJEO 2 V9UJ5hEaWiwMq3lxwKw9 A1R2kF 4 fLUS3NYE 5sFcoMh xgdxQ7t 2 2 S25TIbMLU5FMV6ys4 2ra47EFC7LWzxTF2tSH 2 uwm tczurXngUW 3 gWG1aLfP1Gk DNAv Zh4tWi1QdYjTblw5 1 qN_OnmRhGksD 1 pAJC7fTKPJjaxPP 2 mElj5iV4wfu Jr9Sqekor 1 _Z13N_OO 1 rn 1 HhjFL6Rg 1 2q 5 vdFavgJoOBT4vrKWv LjvEZmSkrs...
result:
ok 10000 test cases ok. (10000 test cases)
Test #9:
score: 0
Accepted
time: 51ms
memory: 14828kb
input:
10000 4 BUqwUvN2v7co K 45 accepted fb4ykhGx9CBzWxLcGYjf F 96 rejected 3X39YaWp0LItH14Owx R 142 rejected 7JGP4qtBonRiKpsKW U 155 rejected 3 Z0cxqdpQ69NGV5wDoht X 92 rejected 1E0aicZDqPhh E 105 accepted a3fvTkSrKXqQipNGs4h K 261 rejected 6 LR6PY6OjDoSaZpT W 33 accepted Et8w1E52xfM27 Q 155 accepted LR6...
output:
1 BUqwUvN2v7co 2 Z0cxqdpQ69NGV5wDoht 1E0aicZDqPhh 1 LR6PY6OjDoSaZpT 3 YX 7f b 4 WqSH sgpEsfgf_Fd buFAkOkQ_F o7VPp 1 coTjuCSsnonAgjYkChE 2 clGo2Z4AMe9Qp GC0Lw1Di 2 IrJ_n_Ym FCCHBTUTGJTbTjEb 1 fkBpEQxhBl21ARSTVR 1 fQzlJS9JEIS97gIIG7p4 6 pqyDmprb2RmUBafc76eR ljfPMl71hE bLED4G7CY_M CVVvEx togG...
result:
ok 10000 test cases ok. (10000 test cases)
Test #10:
score: 0
Accepted
time: 41ms
memory: 15180kb
input:
10000 7 dBv7DiT L 42 rejected dBv7DiT P 123 accepted 7Bj2dZF6Gy7csrXYakI T 131 rejected 9KtuO O 190 accepted BxACEk Q 285 rejected BxACEk Q 291 rejected HK0pq9qsGnlkgAQT L 296 accepted 3 NQgnW3CShrFJYkKdjagN G 53 rejected ZwZCr O 261 accepted ZwZCr P 270 accepted 6 mbGQ7wcZYr9leKBCsFN Z 4 rejected 7...
output:
2 dBv7DiT 9KtuO 1 ZwZCr 2 7s1bgtS 4LUVnW93OFHOl6fJOmXK 4 _g2LouxyEI_BXaOYQWn pz CZNz6k1QgLrHojbY upCvWQnHRgRSQQ 3 q ungF4dKzJt290JMWNgeH t 3 6mCVqSBpHVkrNZ SuBp7xLMGCHgk 4FjAuM44Nzaz6Tc0 1 xXqqS7r1OU 1 YEHiJvhHR8OmUWz 3 m 0WZFvefoPtNo BiasA1Md2ViU 1 MzQD 2 MJJ4n2rC7YHRflGzEL L501za_ktc 1 ...
result:
ok 10000 test cases ok. (10000 test cases)
Test #11:
score: 0
Accepted
time: 0ms
memory: 17240kb
input:
7 110 10 A 0 accepted 0 A 100 accepted 1 A 100 accepted 2 A 100 accepted 3 A 100 accepted 4 A 100 accepted 5 A 100 accepted 6 A 100 accepted 7 A 100 accepted 8 A 100 accepted 9 A 100 accepted 0 B 100 accepted 1 B 100 accepted 2 B 100 accepted 3 B 100 accepted 4 B 100 accepted 5 B 100 accepted 6 B 10...
output:
11 10 0 1 2 3 4 5 6 7 8 9 11 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 100 0 1 2 3 4 5 6 7 8 9 12 100 0 1 2 3 4 5 6 7 8 9 10 36 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 35 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21...
result:
ok 7 test cases ok. (7 test cases)
Test #12:
score: -100
Wrong Answer
time: 41ms
memory: 16292kb
input:
1000 58 8VR4968BiWGrjt0 G 1 accepted KfduBOJVYor3ixLgzUo Y 5 accepted r9l9P_xyc7oagiZS0ZJ G 26 accepted PL3OrMzXRJRVskByRHHl Y 38 accepted 7wL2M4T1PWyv9rJSdzGN N 47 rejected Vu56KH6ZGwSm E 48 rejected 8VR4968BiWGrjt0 D 53 accepted SI7h8yP C 57 rejected aSVEsYSH9PJjsjSAyH N 61 accepted D3UrdM8xI S 71...
output:
5 8VR4968BiWGrjt0 PL3OrMzXRJRVskByRHHl SI7h8yP mn0iyGyqWOakTAs1Qw umqh9D 6 9M 6OSsIJ 3A4BJULiR9S f22a5ba_ze2qsm2_2k uxPAbOmdBcWg64Q52 EYdAeGI 25 19Mbp qF0kRrasPk wd5q6DH XJ9p0AKseAnbt7vmR_ 9sFtbGG4oMjSgmtZh oLi8SUSfzmANlYBZxL io_4OkSzJAGEqNUfs6R Qo8l4lQKg D6SdnJFh6xFQlZehalkc lUs4Rd_AXJR2FP48 qeyR...
result:
wrong answer the numbers are different in the case 204. (test case 204)