QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #661376 | #8230. Submissions | Lavender_Field# | RE | 88ms | 73676kb | C++20 | 7.2kb | 2024-10-20 15:58:29 | 2024-10-20 15:58:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct ques{
int AC_times,submit_times,last_submit;
int first_AC=-1,second_AC=-1,first_submit=-1;
};
struct node{
string name;
int solved,time;
int least_unsolved,del_time_most;
int max_unsolved;
int once_least_solved,most_time_added;
ques pro[27];
}a[N];
bool less_equal_cmp(node i, node j){
if(i.solved != j.solved) return i.solved>j.solved;
return i.time<=j.time;
}
int T,m,cnt,n;
bool has_zero;
map<string,int> ma;
string tmp;
vector<string> ans;
int max_zero_penalty;
void solve(){
scanf("%d",&m);max_zero_penalty=0;
for(int i=1;i<=cnt;i++){
a[i].solved=a[i].time=a[i].least_unsolved=a[i].max_unsolved=0;
a[i].del_time_most=a[i].once_least_solved=a[i].most_time_added=0;
for(int j=1;j<=26;j++){
a[i].pro[j].AC_times=0;
a[i].pro[j].submit_times=0;
a[i].pro[j].first_AC=-1;
a[i].pro[j].second_AC=-1;
a[i].pro[j].first_submit=-1;
a[i].pro[j].last_submit=-1;
}
}
cnt=n=0;
has_zero=0;ans.clear();
ma.clear();
for(int i=1,t;i<=m;i++){
cin>>tmp;
int teamid;
if(ma.count(tmp)==0){
ma[tmp]=++cnt;
a[cnt].name=tmp;
}
teamid=ma[tmp];
char ch[10];scanf("%s",ch);
int pro_id=ch[0]-'A'+1;
scanf("%d",&t);
scanf("%s",ch);
if(ch[0]=='a'){
a[teamid].pro[pro_id].AC_times++;
a[teamid].pro[pro_id].submit_times++;
if(a[teamid].pro[pro_id].AC_times==1){
a[teamid].pro[pro_id].first_AC=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
else if(a[teamid].pro[pro_id].AC_times==2){
a[teamid].pro[pro_id].second_AC=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
if(a[teamid].pro[pro_id].submit_times==1){
a[teamid].pro[pro_id].first_submit=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
a[teamid].pro[pro_id].last_submit=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
else{
a[teamid].pro[pro_id].submit_times++;
if(a[teamid].pro[pro_id].submit_times==1){
a[teamid].pro[pro_id].first_submit=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
a[teamid].pro[pro_id].last_submit=t+20*(a[teamid].pro[pro_id].submit_times-1);
}
}
for(int i=1;i<=cnt;i++){
int teamid=i;
a[teamid].least_unsolved=1e9;
a[teamid].del_time_most=0;
a[teamid].once_least_solved=1e9;
a[teamid].most_time_added=0;
a[teamid].max_unsolved=0;
for(int i=1;i<=26;i++){
if(a[teamid].pro[i].AC_times>=1){
a[teamid].solved++;
a[teamid].time+=a[teamid].pro[i].first_AC;
a[teamid].del_time_most=max(a[teamid].del_time_most,a[teamid].pro[i].first_AC-a[teamid].pro[i].first_submit);
if(a[teamid].pro[i].AC_times==1){
a[teamid].once_least_solved=min(a[teamid].once_least_solved,a[teamid].pro[i].first_AC);
}
else{
a[teamid].most_time_added=max(a[teamid].most_time_added,a[teamid].pro[i].second_AC-a[teamid].pro[i].first_AC);
}
}
else{
if(a[teamid].pro[i].submit_times>=1){
a[teamid].least_unsolved=min(a[teamid].least_unsolved,a[teamid].pro[i].first_submit);
a[teamid].max_unsolved=max(a[teamid].max_unsolved,a[teamid].pro[i].last_submit);
}
}
}
if(a[teamid].solved>=1) n++;
else has_zero=1;
if(a[teamid].solved==0){
// cout<<"zero"<<a[teamid].name<<endl;
max_zero_penalty=max(max_zero_penalty,a[teamid].max_unsolved);
}
}
int gold=min((n-1)/10+1,35);
sort(a+1,a+1+cnt,less_equal_cmp);
// printf("gold %d %d\n",gold,n);
for(int i=1;i<=cnt;i++){
// int least_unsolved,del_time_most;
// int once_least_solved,most_time_added;
if(less_equal_cmp(a[i],a[gold])){
ans.push_back(a[i].name);
}
else if(less_equal_cmp(a[i],a[gold+1])){
// cout<<"?"<<a[i].name<<endl;
node t1=a[i];
if(a[i].least_unsolved!=1e9){
t1.solved++;
t1.time+=a[i].least_unsolved;
}
else{
t1.time-=a[i].del_time_most;
}
if(a[i].solved ==0 && t1.solved == 1 && n%10==0 && gold!=35) gold++;
if(less_equal_cmp(t1,a[gold])){
ans.push_back(a[i].name);continue;
}
if(a[i].solved ==0 && t1.solved == 1 && n%10==0 && gold!=35) gold--;
// printf("why %d %d\n",has_zero,n);
if(has_zero && n%10==0){
if(a[i].solved==0 || a[i].solved>=2){
ans.push_back(a[i].name);continue;
}
else{
// printf("zero %d\n",max_zero_penalty);
if(max_zero_penalty>=a[i].time){
ans.push_back(a[i].name);continue;
}
}
}
// printf()
for(int j=1;j<=gold;j++){
node t2=a[j];
if(a[j].once_least_solved!=1e9){
t2.solved--;
t2.time-=a[j].once_least_solved;
}
else{
t2.time+=a[j].most_time_added;
}
if(t2.solved==0 && n%10==1 && n<=341) continue;
if(less_equal_cmp(a[i],t2)){
ans.push_back(a[i].name);
break;
}
}
}
else{
node t1=a[i];
// cout<<"!"<<a[i].name<<endl;
if(a[i].least_unsolved!=1e9){
t1.solved++;
t1.time+=a[i].least_unsolved;
}
else{
// printf("? %d\n",a[i].del_time_most);
t1.time-=a[i].del_time_most;
}
if(a[i].solved ==0 && t1.solved == 1 && n%10==0 && gold!=35) gold++;
// printf("compare gold %d\n",gold);
if(less_equal_cmp(t1,a[gold])){
ans.push_back(a[i].name);continue;
}
if(a[i].solved ==0 && t1.solved == 1 && n%10==0 && gold!=35) gold--;
}
}
printf("%d\n",ans.size());
for(auto x:ans){
cout<<x<<" ";
}
printf("\n");
}
int main(){
scanf("%d",&T);
while(T--) solve();
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 73388kb
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 ImYourFan LetItRot XuejunXinyoudui1 AllWayTheNorth
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 73676kb
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: 73456kb
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 J I H G F E D C B K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 73408kb
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 B A 2 A K
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 88ms
memory: 73376kb
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
Runtime Error
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 xiLm0TUOF3T tsd 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU ...