QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #669798 | #8230. Submissions | Scene | WA | 1ms | 5868kb | C++14 | 6.9kb | 2024-10-23 19:41:41 | 2024-10-23 19:41:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int read(){
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}
return ret*f;
}
int T,m,n,cnt,ln;
map<string,int> mp;
struct Submission{
int bel,t,pro;
bool knd;
}sub[maxn];
struct Team{
int id,num,plt;
int rec[26][4],pre[26][2]; // 0 first 1 AC 2 AC_sec 3 ed
bool operator<(const Team &B)const{return num>B.num||(num==B.num&&plt<B.plt);}
}tem[maxn],now;
int tot[maxn][26];
bool ok[maxn],ok2[maxn];
string nam,sta;
char p;
int main(){
T=read();
while(T--){
mp.clear();n=0;cnt=0;
m=read();
for(int i=1;i<=m;++i){
cin>>nam>>p>>sub[i].t>>sta;
if(!mp[nam]) mp[nam]=++n;
sub[i].bel=mp[nam];
if(sta[0]=='r'){
sub[i].knd=0;
}else{
sub[i].knd=1;
}
sub[i].pro=p-'A';
if(!(tem[sub[i].bel].rec[sub[i].pro][0])){
tem[sub[i].bel].rec[sub[i].pro][0]=i;
}
if(sub[i].knd){
if(!(tem[sub[i].bel].rec[sub[i].pro][1])){
tem[sub[i].bel].rec[sub[i].pro][1]=i;
tem[sub[i].bel].pre[sub[i].pro][0]=tot[sub[i].bel][sub[i].pro];
}else if(!(tem[sub[i].bel].rec[sub[i].pro][2])){
tem[sub[i].bel].rec[sub[i].pro][2]=i;
tem[sub[i].bel].pre[sub[i].pro][1]=tot[sub[i].bel][sub[i].pro];
}
}
tem[sub[i].bel].rec[sub[i].pro][3]=i;
tot[sub[i].bel][sub[i].pro]++;
}
for(int i=1;i<=n;++i){
tem[i].id=i;
ok[i]=ok2[i]=0;
for(int p=0;p<26;++p){
if(tem[i].rec[p][1]){
tem[i].num++;
tem[i].plt+=sub[tem[i].rec[p][1]].t+20*tem[i].pre[p][0];
}
}
if(tem[i].num) cnt++;
}
ln=min((cnt+9)/10,35);
if(ln==0){
printf("%d\n",n);
for(auto s:mp){
cout<<s.first<<" ";
}
cout<<endl;
for(int i=1;i<=n;++i){
tem[i].plt=0;
tem[i].num=0;
for(int t=0;t<26;++t){
tem[i].rec[t][0]=tem[i].rec[t][1]=tem[i].rec[t][2]=tem[i].rec[t][3]=0;
tem[i].pre[t][0]=tem[i].pre[t][1]=0;
tot[i][t]=0;
}
}
continue;
}
sort(tem+1,tem+n+1);
for(int i=1;i<=n;++i){
if(tem[i].num==tem[i-1].num&&tem[i].plt==tem[i-1].plt){
ok[tem[i].id]=ok2[tem[i].id]=ok2[tem[i-1].id];
if(ok[tem[i].id]) continue;
}
if(i<=ln){
ok[tem[i].id]=1;
continue;
}else if(i==ln+1){
for(int s=1;s<=ln;++s){
now.num=tem[s].num;
now.plt=tem[s].plt;
for(int p=0;p<26;++p){
if(!tem[s].rec[p][1]) continue;
if(!tem[s].rec[p][2]){
if(now.num==tem[s].num){
now.num=tem[s].num-1;
now.plt=tem[s].plt-20*tem[s].pre[p][0]-sub[tem[s].rec[p][1]].t;
}else{
now.plt=max(now.plt,tem[s].plt-20*tem[s].pre[p][0]-sub[tem[s].rec[p][1]].t);
}
}else{
if(now.num==tem[s].num){
now.plt=max(now.plt,tem[s].plt-20*tem[s].pre[p][0]-sub[tem[s].rec[p][1]].t+20*tem[s].pre[p][1]+sub[tem[s].rec[p][2]].t);
}
}
}
if(!now.num){
for(int p=0;p<26;++p){
if(!tem[s].rec[p][1]) continue;
if(!tem[s].rec[p][2]){
;
}else{
if(now.num==tem[s].num){
now.plt=max(now.plt,tem[s].plt-20*tem[s].pre[p][0]-sub[tem[s].rec[p][1]].t+20*tem[s].pre[p][1]+sub[tem[s].rec[p][2]].t);
}
}
}
}
if(!(now<tem[i])){
ok[tem[i].id]=ok2[tem[i].id]=1;
break;
}
}
if(ok[tem[i].id]) continue;
if(cnt%10!=0||ln==35) continue;
for(int s=1;s<=n;++s){
if(tem[s].num) continue;
now.num=1;
now.plt=0;
for(int p=0;p<26;++p){
if(tem[s].rec[p][3]){
now.plt=max(now.plt,sub[tem[s].rec[p][3]].t+20*tot[tem[s].id][p]-20);
}
}
if(!(now<tem[i])){
ok[tem[i].id]=ok2[tem[i].id]=1;
break;
}
}
continue;
}
if(!(tem[i].num)){
if(cnt%10==0&&ln!=35){
ln++;
}
}
now.num=tem[i].num;
now.plt=tem[i].plt;
for(int p=0;p<26;++p){
if(tem[i].rec[p][1]){
if(now.num==tem[i].num){
now.plt=min(now.plt,tem[i].plt-sub[tem[i].rec[p][1]].t-20*tem[i].pre[p][0]+sub[tem[i].rec[p][0]].t);
}
}else if(tem[i].rec[p][0]){
if(now.num==tem[i].num){
now.num=tem[i].num+1;
now.plt=tem[i].plt+sub[tem[i].rec[p][0]].t;
}else{
now.plt=min(now.plt,tem[i].plt+sub[tem[i].rec[p][0]].t);
}
}
}
if(!(tem[ln]<now)){
ok[tem[i].id]=1;
if(!(tem[i].num)){
ln=min((cnt+9)/10,35);
}
continue;
}
ln=min((cnt+9)/10,35);
}
int ans=0;
for(int i=1;i<=n;++i){
if(ok[i]){
ans++;
}
}
printf("%d\n",ans);
for(auto s:mp){
if(ok[s.second]){
cout<<s.first<<" ";
}
}
cout<<endl;
for(int i=1;i<=n;++i){
tem[i].plt=0;
tem[i].num=0;
for(int t=0;t<26;++t){
tem[i].rec[t][0]=tem[i].rec[t][1]=tem[i].rec[t][2]=tem[i].rec[t][3]=0;
tem[i].pre[t][0]=tem[i].pre[t][1]=0;
tot[i][t]=0;
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5800kb
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: 3736kb
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: 1ms
memory: 5792kb
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: 1ms
memory: 5868kb
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)