QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #670000 | #8230. Submissions | anlanyi | WA | 107ms | 3700kb | C++20 | 11.6kb | 2024-10-23 20:13:01 | 2024-10-23 20:13:02 |
Judging History
answer
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define point(n) fixed << setprecision(n)
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0), cout.tie(0);
#define endl '\n'
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<ll, ll> PII;
typedef pair<ll, array<ll, 2>> PIA;
const int N = 1e6 + 10,mod=998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
struct node
{
string s;
int time;
string tu;
};
struct team
{
/* data */
string s;
int num;
int time;
};
void solve()
{
cin >> m ;
map<string ,int >e;
map<string ,array<vector<int > ,26>>now;
vector<vector<node>>pro(30);
for(int i=1;i<=m;i++){
string a,d;int c;
char b;
cin >> a >> b >> c >> d;
node q={a,c,d};
int t=c;
if(d=="rejected")t+=1001;
pro[b-'A'].emplace_back(a,t,d);
now[a][b-'A'].push_back(t);
if(d=="accepted")e[a]=1;
}
n=e.size();
int gold=min(35,(n+9)/10);
for(int i=0;i<26;i++){
sort(all(pro[i]),[&](node a,node b){
return a.time<b.time;
});
}
vector<team>w;
map<string ,array<int ,3>>id;
for(auto &[x,y]:now){
int a=0,b=0;
for(int i=0;i<26;i++){
int ok=0,ti=0;
for(auto g:y[i]){
if(g<1000){
if(!ok){
ti+=g;
}
// if(x=="H")cout<<i<<' '<<g<<'\n';
ok=1;
}else {
if(!ok){
ti+=20;
}
}
}
sort(all(y[i]));
// if(x=="M")cout<<a<<' '<<b<<'\n';
if(ok)a++,b+=ti;
}
// cout<<x<<' '<<a<<' '<<b<<'\n';
w.push_back({x,a,b});
}
sort(all(w),[&](team a,team b){
if(a.num!=b.num)return a.num>b.num;
return a.time<b.time;
});
vector<string >ans;
map<string ,int >dd;
for(int i=0;i<w.size();i++){
auto [a,b,c]=w[i];
dd[a]=i;
id[a]={b,c,i};
if(i){
if(w[i-1].num==w[i].num and w[i-1].time==w[i].time ){
id[a][2]=id[w[i-1].s][2];
}
}
// cout<<id[a][2]<<' ';
}
map<string ,int >ch;
int num=0;
for(int i=0;i<w.size();i++){
if(id[w[i].s][2]<gold)num++;
}
// for(auto [a,b,c]:w){
// cout<<b<<' ';
// cout<<a<<' '<<b<<' '<<c<<'\n';
// }
string ns="",nns="";int na=0,nb=inf,nna=0,nnb=inf;
vector<int >vis(w.size()+10);
//cout<<gold<<'\n';
for(int i=0;i<w.size();i++){
// cout<<w[i].s<<' '<<i<<' '<<id[w[i].s][2]<<'\n';
if(id[w[i].s][2]<gold){
ch[w[i].s]=1;
// cout<<i<<' ';
vis[i]=1;
ns=w[i].s;
na=w[i].num,nb=w[i].time;
}
if(id[w[i].s][2]>=gold and nnb==inf){
// cout<<i<<'\n';
nns=w[i].s;
nna=w[i].num,nnb=w[i].time;
}
}
// cout<<nns<<'\n';
// cout<<gold<<'\n';
int ook=0;
for(int i=0;i<26;i++){
if(pro[i].size()){
for(auto [s,time,tu]:pro[i]){
if(tu=="accepted"){
int a=id[s][0],b=id[s][1],c=id[s][2];
int l=0,r=now[s][i].size()-1;
while(l<r){
int mid=l+r+1>>1;
if(now[s][i][mid]<=time)l=mid;
else r=mid-1;
}
if(c<gold){
if(l==0){
if(l+1<now[s][i].size()){
// for(auto g:now[s][i]){
// cout<<g<<'\n';
// }
if(now[s][i][l+1]<1000){
// cout<<00;
b-=now[s][i][l];
if(now[s][i].back()>1000){
int L=lower_bound(now[s][i].begin(),now[s][i].end(),1001+now[s][i][l])-now[s][i].begin(),
R=lower_bound(now[s][i].begin(),now[s][i].end(),1001+now[s][i][l+1])-now[s][i].begin();
R--;
// cout<<L<<' '<<R<<'\n';
b+=max(0,R-L+1)*20+now[s][i][l+1];
}
}else {
a--;
b-=now[s][i][l];
}
}else {
a--;
b-=now[s][i][l];
}
}
//cout<<s<<' '<<a<<' '<<na<<' '<<b<<' '<<nb<<'\n';
if(a==0){
int nowgold=min((n+8)/10,35);
if(nowgold==gold-1){
}else if(num==gold){
if(nna==a and nnb<=b){
ook=1;
vis[id[nns][2]]=1;
ch[nns]=1;
}else if(nna>a){ ook=1;
// cout<<id[nns][2]<<' ';
vis[id[nns][2]]=1;
ch[nns]=1;
}
}
// cout<<vis[10];
}else
if(num==gold){
// cout<<s<<' '<<a<<' '<<nna<<' '<<b<<' '<<nnb<<'\n';
// cout<<9;
if(nna==a and nnb<=b){
ook=1;
vis[id[nns][2]]=1;
ch[nns]=1;
}else if(nna>a){
ook=1;
// cout<<id[nns][2]<<' ';
vis[id[nns][2]]=1;
ch[nns]=1;
}
// cout<<vis[10];
}
}
}else {
int nowgold=gold;
int a=id[s][0],b=id[s][1],c=id[s][2];
int l=0,r=now[s][i].size()-1;
while(l<r){
int mid=l+r+1>>1;
if(now[s][i][mid]<=time)l=mid;
else r=mid-1;
}
// if(s=="M"){
// cout<<a<<' '<<b<<'\n';
// }
//if(s=="M")cout<<l<<'\n';
if(c>=gold and now[s][i][0]>1000){
// if(s=="M"){
// cout<<9;
// }
a++,b+=now[s][i][l]-1001+l*20;
if(a==1){
nowgold=min((n+10)/10,35);
if(gold==nowgold-1){
if((a==nna and b<nnb)||a>nna){
// if(s=="M"){
// cout<<9;
// }
// cout<<s<<' '<<a<<' '<<nna<<' '<<b<<' '<<nnb<<'\n';
// cout<<s<<'\n';
// ook=1;
vis[c]=1;
ch[s]=1;
// int L=0,R=w.size()-1;
// while(L<R){
// int mid=L+R>>1;
// if(w[mid].num<= a)R=mid;
// else L=mid+1;
// }
// int l=L;
// //cout<<w[l+1].num<<' ';
// L=0,R=w.size()-1;
// while(L<R){
// int mid=L+R+1>>1;
// if(w[mid].num<= a)L=mid;
// else R=mid-1;
// }
// int r=L;
// // cout<<w[r].num<<' ';
// while(l<r){
// int mid=l+r>>1;
// if(w[mid].time<=b)r=mid;
// else l=mid+1;
// }
// // cout<<"+"<<a<<' '<<b<<'\n';
// // cout<<w[l].num<<' '<<w[l].time<<'\n';
// if(w[l].num==a and w[l].time==b){
// // cout<<id[w[l].s][2]<<'\n';
// vis[id[w[l].s][2]]=1;
// }
}else{
// cout<<nns<<' '<<id[nns][2]<<'\n';
// cout<<vis[10]<<'\n';
vis[id[nns][2]]=1;
ook=1;
ch[nns]=1;
// cout<<vis[10]<<'\n';
}
// cout<<vis[10];
}
}else {
if(a==na and b<=nb){
vis[c]=1;
ch[s]=1;
}else if(a>na){
vis[c]=1;
ch[s]=1;
}
}
// if(s=="M"){
// cout<<a<<' '<<na<<' '<<b<<' '<<nb<<'\n';
// }
}
// cout<<vis[11];
}
}
}
}
// for(int i=0;i<w.size();i++){
// // cout<<vis[i]<<' '<<id[w[i].s][2]<<'\n';
// if(vis[id[w[i].s][2]]){
// ch[w[i].s]=1;
// // cout<<i<<' '<<w[i].s<<'\n';
// }
// }
if(ook){
for(auto [a,b,c]:w){
if(id[a][2]==id[nns][2]){
ch[a]=1;
}
}
}
cout<<ch.size()<<'\n';
for(auto g:ch)cout<<g.first<<' ';
cout<<'\n';
}
int main()
{
IOS;
int _ = 1;
cin >> _;
while (_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
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: 0ms
memory: 3588kb
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 jiangly_fan 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
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: 0ms
memory: 3604kb
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: 98ms
memory: 3588kb
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: 107ms
memory: 3652kb
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 tsd xiLm0TUOF3T 2 JP t3 2 77sgqpbTIr_Zt1 fhYPGC8W82NwJTQL 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz wJlbqIU 2 6mbCu5zA eiuF7a_ 1 xy6QBr8ECi 2 PezeyUurYoz7N1iGU ldaKLZb1oS1sS ...
result:
wrong answer the numbers are different in the case 12. (test case 12)