QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #350324 | #8230. Submissions | mc020207# | WA | 69ms | 77892kb | C++17 | 8.0kb | 2024-03-10 17:15:44 | 2024-03-10 17:15:44 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
#define For(i, a, b) for(int i = (a);i <= (b);i++)
#define Rof(i, a, b) for(int i = (a);i >= (b);i--)
#define LL long long
struct Score{
int n,t;
};
void PRINTSCORE(Score x){
cout<<x.n<<","<<x.t<<"\n";
}
bool operator<(Score x,Score y){
if (x.n!=y.n) return x.n<y.n;
return x.t>y.t;
}
bool operator>=(Score x,Score y){
return !(x<y);
}
bool operator==(Score x,Score y){
return (x.n==y.n&&x.t==y.t);
}
bool operator!=(Score x,Score y){
return !(x==y);
}
Score operator+(Score x,Score y){
x.n+=y.n;
x.t+=y.t;
return x;
}
Score operator-(Score x,Score y){
x.n-=y.n;
x.t-=y.t;
return x;
}
int tmp[MAXN];
map<string,int> mp;
string name[MAXN];
typedef pair<int,bool> pib;
vector<pib> sub[MAXN][30];
Score score[MAXN][30];
Score totscore[MAXN];
set<int> li;
bool cmp(int x,int y){return totscore[y]<totscore[x];}
Score calscore(const vector<pib>& a){
int t=0;
bool f=0;
for(pib x:a){
if (x.second){
f=1;
t+=x.first;
break;
}else{
t+=20;
}
}
if (f) return {1,t};
else return {0,0};
}
void Main(){
li.clear();
mp.clear();
int m;cin>>m;
For(i,1,m) For(j,0,26) sub[i][j].clear();
For(i,1,m){
string s;char c;
int t;string sta;
cin>>s>>c>>t>>sta;
if (mp.count(s)==0){
int mpsz=mp.size()+1;
mp[s]=mpsz;
name[mpsz]=s;
}
int id=mp[s];
sub[id][c-'A'].push_back({t,sta=="accepted"});
}
int n=mp.size();
int n1=0;
For(i,1,n){
tmp[i]=i;
totscore[i]={0,0};
For(j,0,25){
score[i][j]=calscore(sub[i][j]);
totscore[i]=totscore[i]+score[i][j];
}
n1+=totscore[i].n>0;
}
totscore[0]={1000000000,0};
sort(tmp+1,tmp+n+1,cmp);
int gold=min((int)ceil(n1*0.1),35);
// printf("n1=%d gold=%d\n",n1,gold);
int nol=-1,nor=-1;
// PRINTSCORE(totscore[tmp[gold]]);
For(iii,1,n){
int x=tmp[iii];
// PRINTSCORE(totscore[x]);
if (totscore[x]>=totscore[tmp[gold]]) li.insert(x);
else{
if (nol==-1) nol=iii,nor=iii;
else{
if (totscore[x]==totscore[tmp[nol]]) nor=iii;
}
}
}
bool haveadd=0;
if (totscore[tmp[nol]]==Score{0,0}) haveadd=1;
// For(i,1,n) cout<<tmp[i]<<" ";
For(iii,1,n){
int x=tmp[iii];
if (totscore[x]>=totscore[tmp[gold]]){ // 本身可以金牌
if (haveadd) continue;
Score maxminus={0,0};
For(j,0,25){
if (score[x][j]==Score{0,0}) continue;
vector<pib> b=sub[x][j];
for (pib &x:b){
if (x.second==1){
x.second=0;
break;
}
}
Score now=calscore(b);
// printf("maxminus={%d,%d},minus={%d,%d}\n",maxminus.n,maxminus.t,(score[x][j]-now).n,(score[x][j]-now).t);
maxminus=max(score[x][j]-now,maxminus);
// printf("maxminus={%d,%d},minus={%d,%d}\n",maxminus.n,maxminus.t,(score[x][j]-now).n,(score[x][j]-now).t);
}
Score now=totscore[x]-maxminus;
int gold2=gold;
if (totscore[x]!=Score{0,0}&&now==Score{0,0}){
gold2=min((int)ceil((n1-1)*0.1),35);
}
if (totscore[tmp[nol]]>=now&&(nol-1<=gold2)){
haveadd=1;
For(i,nol,nor) li.insert(tmp[i]);
}
/* if () */
}else{
Score maxplus={0,0};
int mxt=-1;
For(j,0,25){
if (sub[x][j].empty()) continue;
vector<pib> b=sub[x][j];
b[0].second=1;
Score now=calscore(b);
maxplus=max(now-score[x][j],maxplus);
mxt=max(mxt,sub[x][j].back().first);
}
Score now=totscore[x]+maxplus;
int gold2=gold;
if (totscore[x]==Score{0,0}&&now!=Score{0,0}){
gold2=min((int)ceil((n1+1)*0.1),35);
}
if (now>=totscore[tmp[gold2]]) li.insert(x);
if (totscore[x]==Score{0,0}&&mxt!=-1&&haveadd==0){
Score now={1,mxt};
if (totscore[tmp[nol]]>=now&&nol<=gold2){
For(i,nol,nor) li.insert(tmp[i]);
haveadd=1;
}
}
}
}
cout<<li.size()<<"\n";
for (int x:li) cout<<name[x]<<" ";
cout<<"\n";
// sort(tmp+1,tmp+n+1,cmp);
// For(i,1,n) cout<<name[tmp[i]]<<" "<<totscore[tmp[i]].n<<" "<<totscore[tmp[i]].t<<"\n";
// cout<<"\n";
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while (T--) Main();
}
/*
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 accepted
ImYourFan I 257 accepted
ImYourFan Y 257 accepted
AllWayTheNorth T 264 accepted
XuejunXinyoudui1 J 294 accepted
LetItRot I 299 accepted
LetItRot I 299 rejected
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
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 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 rejected
K K 2 rejected
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 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
*/
/*
8
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 accepted
ImYourFan I 257 accepted
ImYourFan Y 257 accepted
AllWayTheNorth T 264 accepted
XuejunXinyoudui1 J 294 accepted
LetItRot I 299 accepted
LetItRot I 299 rejected
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
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 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 rejected
K K 2 rejected
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 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 77016kb
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: 11ms
memory: 77892kb
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: 7ms
memory: 77024kb
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: 11ms
memory: 77080kb
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: -100
Wrong Answer
time: 69ms
memory: 77092kb
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:
2 M3JytWoaEXxkACy_mBAQ 2 sQ 2 JinbrcS58gNEE5yTSkT 2 cklwBY 1 v_o42YmvEKFwy 2 ftQVK8S_um22w 2 _bQBeFeDpYQhvZcLf9l3 1 KvDcEAIDN 1 H3MUK6 2 gxYo_oCFn2J8aIben 2 _isnlUGK0ddI 2 BERcVjyCp 1 6In2do_50ylch 1 f0r3SXc6brMjT 2 7njYOapSwvogA 1 x 2 y1w3KvxylfxwprRBYw 1 aGedzS 2 iPo0...
result:
wrong answer the numbers are different in the case 1. (test case 1)