QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #669350 | #8230. Submissions | qzez | WA | 114ms | 6068kb | C++14 | 6.7kb | 2024-10-23 18:18:40 | 2024-10-23 18:18:44 |
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];
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]=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]=ok[tem[i-1].id];
if(ok[tem[i].id]) continue;
}
if(i<=ln){
ok[tem[i].id]=1;
if(!(tem[i].num)){
if(cnt%10==0&&ln!=35){
ln++;
}
}
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-20*tem[i].pre[p][0]);
}
}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)){
if(cnt%10==0&&ln!=35){
ln--;
}
}
continue;
}
if(!(tem[i].num)){
if(cnt%10==0&&ln!=35){
ln--;
}
}
if(i!=ln+1) continue;
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]+20*tem[s].pre[p][1]);
}
}
}
if(!now.num){
ln=min((cnt+8)/10,35);
}
if(!(now<tem[i])){
if(s>ln) continue;
if(tem[ln+1]<tem[i]) continue;
ok[tem[i].id]=1;
break;
}
ln=min((cnt+9)/10,35);
}
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]=1;
break;
}
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5840kb
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: 1ms
memory: 5780kb
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: 3856kb
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: 6068kb
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: 114ms
memory: 5864kb
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: 77ms
memory: 5872kb
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 4 ADrO7CHWWKZ_Kefn PezeyUurYoz7N1i...
result:
wrong answer the numbers are different in the case 12. (test case 12)