QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #415547 | #8230. Submissions | ushg8877 | WA | 80ms | 92020kb | C++14 | 3.3kb | 2024-05-20 23:18:31 | 2024-05-20 23:18:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
map<string,int> mp;
int n,m,vid,gl,pre;
struct team{
string name;
ll fs[26],tot;int cnt;bool ps[26],ans;
vector<pair<int,bool> > sub[26];
void init(){
memset(fs,0,sizeof(fs));
memset(ps,0,sizeof(ps));
ans=false;tot=cnt=0;
for(int i=0;i<26;i++) sub[i].clear();
}
void upd(int id){
tot-=fs[id]*ps[id];
vid-=(cnt>0);
cnt-=ps[id];
fs[id]=ps[id]=0;
for(auto i:sub[id])if(!ps[id]){
if(i.second==1){
fs[id]+=i.first;
ps[id]=true;
}else fs[id]+=20;
}
tot+=fs[id]*ps[id];
cnt+=ps[id];
vid+=(cnt>0);
gl=min(35,(int)ceil(vid*0.1));
}
}gp[MAXN];
bool operator >(team &x,team &y){
if(x.cnt!=y.cnt) return x.cnt>y.cnt;
return x.tot<y.tot;
}
bool operator >=(team &x,team &y){
if(x.cnt!=y.cnt) return x.cnt>y.cnt;
return x.tot<=y.tot;
}
void solve(){
cin>>m;
for(int i=1;i<=m;i++) gp[i].init();
n=vid=pre=0;mp.clear();
for(int i=1;i<=m;i++){
string team,pro,sta;ll tim;
cin>>team>>pro>>tim>>sta;
if(!mp.count(team)){
mp[team]=++n;
gp[n].name=team;
}
int id=mp[team],pid=pro[0]-'A';
gp[id].sub[pid].push_back(MP(tim,sta[0]=='a'));
}
for(int i=1;i<=n;i++) for(int j=0;j<26;j++) gp[i].upd(j);
sort(gp+1,gp+n+1,[&](team &x,team &y){return x>y;});
// cout<<"Valid Team: "<<vid<<'\n';
// cout<<"Goal: "<<gl<<'\n';
// for(int i=1;i<=n;i++)
// cout<<"Rank "<<i<<": "<<gp[i].name<<' '<<gp[i].tot<<' '<<gp[i].cnt<<'\n';
for(int i=1;i<=n;i++) if(gp[i]>=gp[gl]) gp[i].ans=true;
auto upd=[&](int sp){
// cout<<"Check sp "<<sp<<' '<<gl<<'\n';
int l=1,r=n,mid=0,cnt=0;
while(l<r){
mid=(l+r+1)>>1;
cnt=mid-1-(sp<mid)+(gp[sp]>gp[mid]);
if(cnt<gl) l=mid;
else r=mid-1;
}
cnt=l-1-(sp<l)+(gp[sp]>gp[l]);
if(cnt<gl-1&&gp[l]>=gp[sp]&&gp[sp]>=gp[l+1]) l=sp;
if(gp[sp]>=gp[l]){
// cout<<"Special "<<sp<<' '<<l<<" is OK!\n";
gp[sp].ans=true;
}
int spl=l;
l=1,r=n;
while(l<r){
mid=(l+r+1)>>1;
if(gp[mid]>=gp[spl]) l=mid;
else r=mid-1;
}
// cout<<"Here "<<spl<<' '<<l<<'\n';
// cout<<"Detail: "<<gp[sp].cnt<<' '<<gp[sp].tot<<'\n';
pre=max(pre,l);
};
for(int i=1;i<=n;i++){
for(int j=0;j<26;j++){
bool fa=false,fr=false;
for(auto &k:gp[i].sub[j]){
// cout<<"Get! "<<' '<<k.first<<' '<<k.second<<'\n';
if(k.second==0&&fr==false){
fr=true;
k.second=1;
gp[i].upd(j);
upd(i);
k.second=0;
gp[i].upd(j);
}else if(k.second==1&&fa==false){
fa=true;
k.second=0;
gp[i].upd(j);
upd(i);
k.second=1;
gp[i].upd(j);
}
}
fr=false;
for(int k=gp[i].sub[j].size()-1;k>=0;k--)
if(gp[i].sub[j][k].second==0&&fr==false){
fr=true;
gp[i].sub[j][k].second=1;
gp[i].upd(j);
upd(i);
gp[i].sub[j][k].second=0;
gp[i].upd(j);
}
}
}
for(int i=1;i<=pre;i++) gp[i].ans=true;
int cnt=0;
for(int i=1;i<=n;i++) cnt+=gp[i].ans;
cout<<cnt<<'\n';
for(int i=1;i<=n;i++) if(gp[i].ans) cout<<gp[i].name<<' ';
cout<<'\n';
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
int _;cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 91996kb
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 XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 12ms
memory: 91940kb
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: 12ms
memory: 91964kb
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: 11ms
memory: 91932kb
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: 80ms
memory: 91996kb
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: 72ms
memory: 92020kb
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 pVWDEz 3BQ 2 tg buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU ...
result:
wrong answer the numbers are different in the case 22. (test case 22)