QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692739#8230. Submissionsmiaomiaomiao#WA 112ms3868kbC++176.1kb2024-10-31 14:58:262024-10-31 14:58:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 14:58:36]
  • 评测
  • 测评结果:WA
  • 用时:112ms
  • 内存:3868kb
  • [2024-10-31 14:58:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x) for (int i=0;i<(int)x;i++)
#define fore(i,x) for (auto &i:x)
#define For(i,x) for (int i=1;i<=(int)x;i++)
#define ll long long
#define vi vector<int>
#define pii pair<int,int>

// bigger is better

ostream &operator << (ostream &out,const pii &p){
    out<<"{"<<p.first<<", "<<p.second<<"}";
    return out;
}

bool operator < (const pii &a,const pii &b){
    if (a.first ==b.first){
        return a.second>b.second;
    }else{
        return a.first<b.first;
    }
}

bool operator > (const pii &a,const pii &b){
    if (a.first ==b.first){
        return a.second<b.second;
    }else{
        return a.first>b.first;
    }
}

bool operator <= (const pii &a,const pii &b){
    return a==b || a<b;
}


bool operator >= (const pii &a,const pii &b){
    return a==b || a>b;
}

class Problem{
public:
    vector <pair<int,bool> > submission;
    int ac=0;

    void insert(const int &t,const bool &f){
        ac+=f;
        submission.emplace_back(t,f);
    }
};


class Team{
public:
    string name;
    unordered_map <char,Problem> prob;

    void insert(const char &c, const int &t,const bool &f){
        prob[c].insert(t,f);
    }

    pii now={0,0},good,bad;
    int biggest_plt=0;
    int can_wa=-1;
    int can_ac=-1;
    int opt=0;
    int fail_opt=0;
    bool ok=0;

    void calc(){
        for (auto &pb:prob){
            int fail=0;
            int aced=0;
            int first_ac_plet = -1;
            int first_fail = -1;
            int lst_fail = 0;

            fore(i,pb.second.submission){
                if (i.second==0){
                    fail+=20;
                    if (first_fail == -1) first_fail = i.first;
                    // lst_fail = i.first;
                    lst_fail = max(lst_fail,i.first);
                }else{
                    if (aced==0){
                        now.first++;
                        now.second+=i.first+fail;
                        first_ac_plet = i.first + fail;
                    }else if (aced==1){
                        int val = i.first + fail + 20 - first_ac_plet;
                        fail_opt = max(fail_opt,val);
                    }
                    aced++;
                }
            }

            if (aced == 0) biggest_plt = max(biggest_plt,lst_fail + fail-20);

            if (aced && first_fail!=-1){
                opt=max(opt,first_ac_plet-first_fail);
            }

            if (aced==1){
                if (can_wa==-1 || can_wa>first_ac_plet) can_wa=first_ac_plet;
            }else if (aced==0){
                if (can_ac==-1 || can_ac>first_fail) can_ac=first_fail;
            }
        }
        if (can_ac!=-1){
            good={now.first+1, now.second+can_ac};
        }else{
            good={now.first,now.second-opt};
        }
        if (can_wa!=-1){
            bad={now.first-1, now.second-can_wa};
        }else{
            bad={now.first,now.second-fail_opt};
        }
    }
};


unordered_map <string,Team> team;
vector <Team> t;
pii gold;



bool cmp(const Team& a,const Team&b){
    return a.now>b.now;
}


int vaild_team = 0;

void calc_normal(){
    gold = t[max(min(35,(vaild_team+9)/10)-1, 0)].now;
    int should_g = min(35,(vaild_team+9)/10);
    int real_g=0;
    pii bad={100000,0},silver_head = {0,0};
    
    // cout<<"vaild "<<vaild_team<<endl;
    // cout<<"Gold "<<gold<<endl; 

    fore(i,t){
        // cout<<i.name<<" "<<i.good<<" "<<i.now<<" "<<i.bad<<endl;
        if (i.now>=gold){
            i.ok=1;
            if (i.bad.first!=0) bad=min(bad,i.bad);
            real_g++;
        }else{
            if (i.now.first==0) continue;
            if (silver_head == pii{0,0}) silver_head = i.now;
            if (i.good>=gold || (real_g<=should_g && i.now==silver_head && i.now>=bad)){
                i.ok=1;
            }
        }
    }

}

void calc_plus(){
    int biggest_plt=0;

    fore(i,t){
        if (i.now==pii{0,0} && i.good.first){
            biggest_plt = max(biggest_plt,i.biggest_plt);
        }
    }
    if (biggest_plt==0) return;
    pii new_vaild = {1,biggest_plt};

    // cout<<"nv"<<new_vaild<<endl;
    int vaild_team = ::vaild_team+1;
    gold = t[max(min(35,(vaild_team+9)/10)-1, 0)].now;

    // gold = max(gold,new_vaild);
    if (new_vaild>gold) gold=new_vaild;

    // cout<<"plus Gold "<<gold<<endl; 

    fore(i,t){
        // cout<<i.name<<" "<<i.good<<" "<<i.now<<" "<<i.bad<<endl;
        if (i.now>=gold ){
            i.ok=1;
        }else if (i.now.first==0 && i.good.first) {
            if (i.good>=gold){
                i.ok=1;
            }
        }
    }
}

void calc_minus(){
    bool ok=0;
    gold = t[max(min(35,(vaild_team+9)/10)-1, 0)].now;


    fore(i,t){
        if (i.now>=gold && i.bad==pii{0,0}) ok=1;
    }

    if (!ok) return;

    int vaild_team = ::vaild_team-1;
    gold = t[min((int)t.size(), min(35,(vaild_team+9)/10)+1 )-1].now;
    
    // cout<<"Gold minus"<<gold<<endl; 

    fore(i,t){
        // cout<<i.name<<" "<<i.good<<" "<<i.now<<" "<<i.bad<<endl;
        if (i.now>=gold){
            i.ok=1;
        }
    }
}

void solve(){
    int n;
    cin>>n;

    team.clear();
    t.resize(0);

    rep(i,n){
        string s;
        char p;
        int t;
        string ac;
        cin>>s>>p>>t>>ac;
        team[s].name=s;
        team[s].insert(p,t,ac=="accepted");
    }


    vaild_team = 0;
    
    for (auto &i:team){
        i.second.calc();
        t.push_back(i.second);
        if (i.second.now.first) vaild_team ++;
    }


    sort(t.begin(),t.end(),cmp);

    calc_normal();
    calc_plus();
    calc_minus();



    vector <string> ans;

    fore(i,t){
        if (i.ok) ans.push_back(i.name);
    }

    cout<<ans.size()<<endl;
    for (auto &i:ans){
        cout<<i<<" ";
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen("input.txt","r",stdin);
    int T;
    cin>>T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

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: 3644kb

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: 0ms
memory: 3868kb

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 G F H B E I D C K 
1
A 

result:

ok 2 test cases ok. (2 test cases)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3616kb

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: 112ms
memory: 3864kb

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: 38ms
memory: 3684kb

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:

3
Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq 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 _Yej1PrINtyd...

result:

wrong answer the numbers are different in the case 1. (test case 1)