QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #550140 | #8230. Submissions | _UMqwq_ | WA | 109ms | 130868kb | C++20 | 4.0kb | 2024-09-07 10:02:03 | 2024-09-07 10:02:04 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define MAXN 100010
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
int T,n,m,srt[MAXN];
map<string,int>id;
struct tnode{int tid,pid,tic,sid,cnt;}sub[MAXN];
struct Node{
string tid;
int cnt,tic,sub[30];
pii fir[30],nxt[30];
void clear(){
for(int i=0;i<26;i++)fir[i]=nxt[i]=mp(0,0),sub[i]=0;
cnt=tic=0;
}
}team[MAXN];
void ac(int x,int p,int tic){
team[x].sub[p]++;
if(!team[x].fir[p].se){
team[x].fir[p]=mp(tic,team[x].sub[p]);
team[x].cnt++,team[x].tic+=tic+(team[x].sub[p]-1)*20;
}
else if(!team[x].nxt[p].se)team[x].nxt[p]=mp(tic,team[x].sub[p]);
}
void wa(int x,int p,int tic){team[x].sub[p]++;}
bool ans[MAXN];
int bel[MAXN],tot;vector<int>tv[MAXN];
struct qnode{int tid,cnt,tic,tc,tag;};
bool operator<(qnode a,qnode b){
return a.cnt==b.cnt?(a.tic==b.tic?a.tid<b.tid:a.tic<b.tic):a.cnt>b.cnt;
}
set<qnode>s;
void update(int ban,int tid){
vector<int>rest;
for(auto i:tv[tid]){
if(i!=ban)ans[i]=1;
else rest.pb(i);
}
swap(tv[tid],rest);
}
void update(int tid,qnode now,int cg){
if(!cg)return;
s.insert(now);auto it=s.begin();int cnt=0,tic=0;//cerr<<"upd:"<<cg<<endl;
for(;cg>0;it++){
int nc=it->tc;
if(it->tid==now.tid&&!it->tag)nc--;
update(!it->tag?tid:0,it->tid);cnt=it->cnt,tic=it->tic;cg-=nc;
}//cerr<<"oc:"<<cnt<<' '<<tic<<endl;
for(;it!=s.end()&&it->cnt==cnt&&it->tic==tic;it++){
int nc=it->tc;
if(it->tid==now.tid&&!it->tag)nc--;
update(!it->tag?tid:0,it->tid);
}
s.erase(s.find(now));
}
signed main(){
scanf("%lld",&T);
while(T--){
for(int i=1;i<=n;i++)ans[i]=0;
s.clear();n=0;id.clear();
scanf("%lld",&m);
for(int i=1;i<=m;i++){
string tid,pid,sid;int tic;
cin>>tid>>pid>>tic>>sid;
if(!id[tid])id[tid]=++n,team[n].clear(),team[n].tid=tid;
if(sid=="accepted")ac(id[tid],pid[0]-'A',tic),sub[i]=(tnode){id[tid],pid[0]-'A',tic,1,team[id[tid]].sub[pid[0]-'A']};
else wa(id[tid],pid[0]-'A',tic),sub[i]=(tnode){id[tid],pid[0]-'A',tic,0,team[id[tid]].sub[pid[0]-'A']};
}
int vld=0;tot=0;
for(int i=1;i<=n;i++)vld+=(team[i].cnt>0),srt[i]=i;
sort(srt+1,srt+n+1,[&](int x,int y){
return team[x].cnt==team[y].cnt?(team[x].tic<team[y].tic):team[x].cnt>team[y].cnt;
});
for(int l=1,r;l<=n;l=r+1){
int cnt=team[srt[l]].cnt,tic=team[srt[l]].tic;
for(r=l;r<n&&team[srt[r+1]].cnt==cnt&&team[srt[r+1]].tic==tic;r++);
tot++;tv[tot].clear();
for(int i=l;i<=r;i++)bel[srt[i]]=tot,tv[tot].pb(srt[i]);
s.insert((qnode){tot,cnt,tic,r-l+1,0});
}
update(0,(qnode){0,0,0,0,0},min(35ll,(vld+9)/10));//cerr<<"000"<<endl;
for(int i=1;i<=m;i++){
int tid=sub[i].tid,j=sub[i].pid,tic=sub[i].tic,cnt=sub[i].cnt;
if(!sub[i].sid){
if(team[tid].fir[j].se&&cnt>team[tid].fir[j].se)continue;
int ncnt=team[tid].cnt+(!team[tid].fir[j].se);
int ntic=team[tid].tic,nvld=vld;
if(team[tid].fir[j].se)ntic-=team[tid].fir[j].fi+(team[tid].fir[j].se-1)*20;
ntic+=tic+(cnt-1)*20;
if(!team[tid].cnt&&ncnt)nvld++;
// cerr<<"changewa:"<<i<<' '<<team[tid].tid<<' '<<team[tid].cnt<<' '<<team[tid].tic<<endl;
// cerr<<"now:"<<ncnt<<' '<<ntic<<' '<<nvld<<endl;
update(tid,(qnode){bel[tid],ncnt,ntic,1,1},min(35ll,(nvld+9)/10));
}else{
if(cnt>team[tid].fir[j].se)continue;
int ncnt=team[tid].cnt-(!team[tid].nxt[j].se);
int ntic=team[tid].tic,nvld=vld;
ntic-=team[tid].fir[j].fi+(team[tid].fir[j].se-1)*20;
if(team[tid].nxt[j].se)ntic+=team[tid].nxt[j].fi+(team[tid].nxt[j].se-1)*20;
if(team[tid].cnt&&!ncnt)nvld--;
// cerr<<"changeac:"<<i<<' '<<team[tid].tid<<' '<<team[tid].cnt<<' '<<team[tid].tic<<endl;
// cerr<<"now:"<<ncnt<<' '<<ntic<<' '<<nvld<<endl;
update(tid,(qnode){bel[tid],ncnt,ntic,1,1},min(35ll,(nvld+9)/10));
}
}
int sum=0;
for(int i=1;i<=n;i++)sum+=ans[i];
printf("%lld\n",sum);
for(int i=1;i<=n;i++)
if(ans[i])cout<<team[i].tid<<' ';
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 128824kb
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: 7ms
memory: 129048kb
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: 3ms
memory: 130868kb
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: 7ms
memory: 130780kb
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: 103ms
memory: 128752kb
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: 109ms
memory: 128756kb
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 4 ldaKLZb1oS1sS _Yej1PrINtydmOudwo...
result:
wrong answer the numbers are different in the case 12. (test case 12)