QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #344556 | #8230. Submissions | zzuqy | WA | 3ms | 11512kb | C++14 | 4.9kb | 2024-03-04 19:30:46 | 2024-03-04 19:30:46 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200009
using namespace std;
int a[N][26][3];//0 now;1 highest;2 lowest
unordered_map<string,int>mp;
unordered_set<int>ans;
string rmp[N];
int n,n2;
bool cmp(const pair<int,int> &a,const pair<int,int>&b){
if(a.first>b.first)return 1;
if(a.first<b.first)return 0;
if(a.second<b.second)return 1;
return 0;
}
struct mapstruct{
bool operator()(const pair<int,int> &a,const pair<int,int>&b){
return cmp(a,b);
}
};
int calcgold(int n){
return min((n+9)/10,35);
}
map<pair<int,int>,vector<int>,mapstruct>gold;
pair<int,int>line;
void handle(){
int x=calcgold(n2);
int cnt=0;
for(auto i:gold){
if(cnt<x)for(auto j:i.second)ans.insert(j);
else break;
cnt+=i.second.size();
//cout<<cnt<<"?"<<x<<endl;
}
}
void del(int x,pair<int,int>score){
if(score.first>0)n2--;
if(!cmp(line,score)){
for(int i=0;i<gold[score].size();i++){
if(gold[score][i]==x){
swap(gold[score][i],gold[score][gold[score].size()-1]);
gold[score].pop_back();
break;
}
}
if(gold[score].size()==0)gold.erase(score);
}
}
void add(int x,pair<int,int>score){
if(score.first>0)n2++;
//cout<<score.first<<" "<<score.second<<endl;
if(!cmp(line,score))gold[score].push_back(x);
}
void query(int x,pair<int,int>normal,pair<int,int>score){
del(x,normal);
add(x,score);
handle();
del(x,score);
add(x,normal);
}
void solve(){
mp.clear();n=n2=0;
ans.clear();gold.clear();
int m;cin>>m;
while(m--){
string s;char c;int t;string p;
cin>>s>>c>>t>>p;
if(mp[s]==0){
mp[s]=++n;rmp[n]=s;
for(int i=0;i<26;i++)a[n][i][0]=a[n][i][1]=a[n][i][2]=-1000000000;
}
int x=mp[s],id=c-'A';
if(p=="accepted"){
if(a[x][id][0]<0)a[x][id][0]=a[x][id][0]+1000000000+t,a[x][id][2]+=20;
else a[x][id][2]=a[x][id][2]+1000000000+t;
//cout<<x<<" "<<id<<" "<<a[x][id][2]<<endl;
if(a[x][id][1]<0)a[x][id][1]=t;
}
if(p=="rejected"){
if(a[x][id][0]<0)a[x][id][0]+=20;
if(a[x][id][1]<0)a[x][id][1]=t;
if(a[x][id][2]<0)a[x][id][2]+=20;
}
}
for(int i=1;i<=n;i++){
int c=0,p=0;
for(int j=0;j<26;j++)if(a[i][j][0]>=0)c++,p+=a[i][j][0];
gold[make_pair(c,p)].push_back(i);
if(c>0)n2++;
//cout<<rmp[i]<<" "<<c<<" "<<p<<endl;
}
int cnt=0;
for(auto it:gold){
cnt+=it.second.size();
if(cnt>calcgold(n2)){
line=it.first;
break;
}
}
while(1){
auto it=gold.end();it--;
if(cmp(line,(*it).first))gold.erase(it);
else break;
}
handle();
for(int i=1;i<=n;i++){
pair<int,int>best=make_pair(0,0),worst=make_pair(1000,0),normal=make_pair(0,0);
for(int y=0;y<26;y++)if(a[i][y][0]>=0)normal.first++,normal.second+=a[i][y][0];
for(int x=0;x<26;x++){
int c=0,p=0;
for(int y=0;y<26;y++){
if(x==y){if(a[i][y][1]>=0)c++,p+=a[i][y][1];}
else {if(a[i][y][0]>=0)c++,p+=a[i][y][0];}
}
if(cmp(make_pair(c,p),best))best=make_pair(c,p);
}
for(int x=0;x<26;x++){
int c=0,p=0;
for(int y=0;y<26;y++){
if(x==y){if(a[i][y][2]>=0)c++,p+=a[i][y][2];}
else {if(a[i][y][0]>=0)c++,p+=a[i][y][0];}
}
if(cmp(worst,make_pair(c,p)))worst=make_pair(c,p);
}
pair<int,int>what=make_pair(0,0);
for(int x=0;x<26;x++){
int c=0,p=0;
for(int y=0;y<26;y++){
if(x==y){if(a[i][y][2]>=0)c++,p+=a[i][y][2];}
else {if(a[i][y][0]>=0)c++,p+=a[i][y][0];}
}
if(c>normal.first&&p>what.second)what=make_pair(c,p);
}
//cout<<normal.first<<"-"<<normal.second<<" ";
//cout<<best.first<<"-"<<best.second<<" ";
//cout<<worst.first<<"-"<<worst.second<<" ";
//cout<<what.first<<"-"<<what.second<<" ";cout<<endl;
query(i,normal,best);
query(i,normal,worst);
if(what.first==normal.first+1)query(i,normal,best);
}
cout<<ans.size()<<endl;
for(auto i:ans)cout<<rmp[i]<<" ";cout<<endl;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int t;cin>>t;
while(t--)solve();
return 0;
}
/*
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
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 10744kb
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 ImYourFan LetItRot XuejunXinyoudui1 AllWayTheNorth
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 11400kb
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: -100
Wrong Answer
time: 0ms
memory: 11512kb
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:
2 K A 1 A
result:
wrong answer the numbers are different in the case 1. (test case 1)