QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #324313 | #8230. Submissions | ucup-team987# | WA | 44ms | 10668kb | C++20 | 3.4kb | 2024-02-10 17:46:33 | 2024-02-10 17:46:35 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
int M;
int C[1<<17];
string Cs[1<<17];
int P[1<<17];
int T[1<<17];
bool S[1<<17];
vector<pair<int,bool> >Sub[1<<17][26];
void solve()
{
cin>>M;
vector<string>team_name(M);
for(int i=0;i<M;i++)
{
string s;
char Pc;
cin>>Cs[i]>>Pc>>T[i]>>s;
S[i]=s[0]=='a';
P[i]=Pc-'A';
team_name[i]=Cs[i];
}
sort(team_name.begin(),team_name.end());
team_name.erase(unique(team_name.begin(),team_name.end()),team_name.end());
if(team_name.size()==1)
{
cout<<"1\n"<<team_name[0]<<"\n";
return;
}
for(int i=0;i<team_name.size();i++)for(int j=0;j<26;j++)Sub[i][j].clear();
//vector<array<vector<pair<int,bool> >,26> >Sub(team_name.size());
for(int i=0;i<M;i++)
{
C[i]=lower_bound(team_name.begin(),team_name.end(),Cs[i])-team_name.begin();
Sub[C[i]][P[i]].push_back(make_pair(T[i],S[i]));
}
int N=0;
vector<int>AC(team_name.size()),Penalty(team_name.size());
vector<pair<pair<int,int>,int> >leader(team_name.size());
for(int i=0;i<team_name.size();i++)
{
int penalty=0,ac=0;
for(int j=0;j<26;j++)if(Sub[i][j].size())
{
int k=0;
while(k<Sub[i][j].size()&&!Sub[i][j][k].second)k++;
if(k==Sub[i][j].size())continue;
penalty+=k*20+Sub[i][j][k].first;
ac++;
}
AC[i]=ac;
Penalty[i]=penalty;
leader[i]=make_pair(make_pair(-ac,penalty),i);
if(ac>0)N++;
}
sort(leader.begin(),leader.end());
vector<int>WIN(team_name.size()+1);
{//orig
int w=min(35,(N+9)/10);
if(w>=1)
{
pair<int,int>p=leader[w-1].first;
WIN[0]++;
WIN[upper_bound(leader.begin(),leader.end(),make_pair(p,(int)1e9))-leader.begin()]--;
}
}
for(int id=0;id<team_name.size();id++)
{
int i=leader[id].second;
auto check=[&](int ac,int penalty,int n){
int w=min((n+9)/10,35);
if(w==0)return;
pair<int,int>np=make_pair(-ac,penalty);
pair<int,int>p=leader[id<=w-1?w:w-1].first;
if(np<=p)
{
WIN[id]++;WIN[id+1]--;
p=np;
if(w>=2)p=max(p,leader[id<=w-2?w-1:w-2].first);
}
int r=upper_bound(leader.begin(),leader.end(),make_pair(p,(int)1e9))-leader.begin();
WIN[0]++;
WIN[r]--;
if(id<r)WIN[id]--,WIN[id+1]++;
};
for(int j=0;j<26;j++)if(Sub[i][j].size())
{
int fa=-1,sa=-1;
for(int k=0;k<Sub[i][j].size();k++)if(Sub[i][j][k].second)
{
if(fa==-1)fa=k;
else if(sa==-1)sa=k;
}
if(fa==-1)
{//no ac
for(int k=0;k<Sub[i][j].size();k++)
{
int ac=AC[i]+1;
int penalty=Penalty[i]+k*20+Sub[i][j][k].first;
int n=N+(AC[i]==0);
check(ac,penalty,n);
}
}
else
{
for(int k=0;k<fa;k++)
{
int ac=AC[i];
int penalty=Penalty[i]-(fa-k)*20+Sub[i][j][k].first;
check(ac,penalty,N);
}
{
int ac=AC[i],penalty=Penalty[i];
penalty-=fa*20+Sub[i][j][fa].first;
if(sa==-1)ac--;
else penalty+=sa*20+Sub[i][j][sa].first;
check(ac,penalty,N-(ac==0));
}
}
}
}
vector<string>ans;
for(int id=0;id<team_name.size();id++)
{
WIN[id+1]+=WIN[id];
if(WIN[id]>0)
{
int i=leader[id].second;
ans.push_back(team_name[i]);
}
}
cout<<ans.size()<<"\n";
for(int i=0;i<ans.size();i++)cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
for(;T--;)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9244kb
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 TS1 TSxingxing10 4 AllWayTheNorth ImYourFan LetItRot XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 4ms
memory: 10492kb
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: 10384kb
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 B C D E F G H I J K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 4ms
memory: 10668kb
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: 28ms
memory: 9776kb
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 4Vf5RXaTmySkFcXgHLOh 1...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Wrong Answer
time: 44ms
memory: 10148kb
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 Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T tsd 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU _Yej1PrINty...
result:
wrong answer the numbers are different in the case 953. (test case 953)