QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #669538 | #8230. Submissions | anlanyi | WA | 0ms | 3944kb | C++20 | 9.0kb | 2024-10-23 18:56:48 | 2024-10-23 18:56:48 |
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=="K")cout<<i<<' '<<g<<'\n';
ok=1;
}else {
if(!ok){
ti+=20;
}
}
}
sort(all(y[i]));
// if(x=="K")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]<<' ';
}
int num=0;
// 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){num++;
// 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){
nns=w[i].s;
nna=w[i].num,nnb=w[i].time;
}
}
// cout<<gold<<'\n';
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(num==gold){
if(nna==a and nnb<=b){
vis[id[nns][2]]=1;
}else if(nna>a){
// cout<<id[nns][2]<<' ';
vis[id[nns][2]]=1;
}
}
}
}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=="K"){
// cout<<a<<' '<<b<<'\n';
// }
//if(s=="K")cout<<l<<'\n';
if(c>=gold and now[s][i][0]>1000){
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){
vis[c]=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{
vis[id[nns][2]]=1;
}
}
}else {
if(a==na and b<=nb){
vis[c]=1;
}else if(a>na){
vis[c]=1;
}
}
// if(s=="K"){
// cout<<a<<' '<<na<<' '<<b<<' '<<nb<<'\n';
// }
}
}
}
}
}
map<string ,int >ch;
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';
}
}
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: 3920kb
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: 3692kb
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: 3944kb
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: -100
Wrong Answer
time: 0ms
memory: 3692kb
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:
11 A B C D E F G H I J K 2 A K
result:
wrong answer the numbers are different in the case 1. (test case 1)