QOJ.ac

QOJ

Type: General Discussion

Status: Closed

Posted by: Hussein

Posted at: 2026-02-11 10:17:46

Last updated: 2026-02-13 00:42:36

Back to Problem

求调

这个代码 WA 6 了,求大佬帮我调题,十分感谢:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sort stable_sort
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
typedef double db;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}
ll quick_pow(ll a, ll b, const ll p) { if (b == 1) { return a * b % p;} if (b == 0) { return 1 % p;} ll x = quick_pow(a, b / 2, p); if (b & 1) { return (1ll * x * x % p * a) % p;} return (1ll * x * x) % p;}
const ll mod = 1e9 + 7;
// head

const int N = 201000, inf = 1e9;
int TC = 1, m;

struct Problem {
    char id;
    int firPen, secPen;
    int firSub, lstSub;
    int subCnt;
    Problem(char _id = '\0') : id(_id), firPen(-1), secPen(-1), firSub(-1), subCnt(0) {}
    void newSubmission(int t, bool ac) {
        subCnt++;
        lstSub = t;
        if (firSub == -1) 
            firSub = t;
        if (ac) {
            int penalty = t + 20 * (subCnt - 1);
            if (firPen == -1) 
                firPen = penalty;
            else if (secPen == -1) 
                secPen = penalty;
        }
    }
    int getPenalty() {
        return firPen == -1 ? 0 : firPen;
    }
    int getScore() {
        return firPen != -1;
    }
    int becomeWeak() {
        return firPen == -1 ? 0 : (secPen == -1 ? inf - firPen : secPen - firPen);
    }
    int becomeStronger() {
        return firPen == -1 ? inf - firPen : firPen - firSub;
    }
    int becomeAC() {
        return firPen == -1 ? lstSub + 20 * (subCnt - 1) : -1;
    }
};

vector<vector<Problem>> probs;

struct Team {
    int id, score, penalty;
    Team(int _id = -1) : id(_id), score(0), penalty(0) {}
    void newSubmission(char tid, int t, bool ac) {
        auto &prob = probs[id];
        int pid = -1;
        for (int i = 0; i < SZ(prob); i++) 
            if (prob[i].id == tid) {
                pid = i;
                break;
            }
        if (pid == -1) {
            pid = SZ(prob);
            prob.pb(tid);
        }
        score -= prob[pid].getScore();
        penalty -= prob[pid].getPenalty();
        prob[pid].newSubmission(t, ac);
        score += prob[pid].getScore();
        penalty += prob[pid].getPenalty();
    }
    void becomeWeak() {
        auto &prob = probs[id];
        int delta = 0;
        for (auto p : prob) 
            delta = max(delta, p.becomeWeak());
        if (delta >= inf / 2) {
            score--;
            penalty -= inf - delta;
        }
        else 
            penalty += delta;
    }
    void becomeStronger() {
        auto &prob = probs[id];
        int delta = 0;
        for (auto p : prob) 
            delta = max(delta, p.becomeStronger());
        if (delta >= inf / 2) {
            score++;
            penalty += inf - delta;
        }
        else 
            penalty -= delta;
    }
    void becomeAC() {
        auto &prob = probs[id];
        int delta = -1;
        for (auto p : prob) 
            delta = max(delta, p.becomeAC());
        if (delta >= 0) {
            score++;
            penalty += delta;
        }
    }
};

bool operator < (const Team &a, const Team &b) {
    return (a.score != b.score) ? (a.score > b.score) : (a.penalty < b.penalty);
}
bool operator == (const Team &a, const Team &b) {
    return a.score == b.score && a.penalty == b.penalty;
}

map<string, int> team_name;
vector<string> names;
vector<Team> teams;

int pos(string s) {
    if (!team_name.count(s)) {
        team_name[s] = SZ(team_name);
        teams.pb(SZ(teams));
        names.pb(s);
        probs.pb({});
    }
    return team_name[s];
}

inline void solve() {
    probs.clear();
    teams.clear();
    team_name.clear();
    names.clear();
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        string name, result;
        int time;
        char problem;
        cin >> name >> problem >> time >> result;
        teams[pos(name)].newSubmission(problem, time, result == "accepted");
    }
    int teamCnt = SZ(teams), okTeam = 0;
    for (auto team : teams) 
        okTeam += team.score >= 1;
    int goldCnt = min(35, (okTeam + 9) / 10);
    VI rank(teamCnt), canGold(teamCnt);
    sort(all(teams));
    for (int i = 0, j; i < teamCnt; i = j) {
        j = i;
        while (j < teamCnt && teams[i] == teams[j]) 
            rank[j++] = i;
    }
    int hr = lower_bound(all(rank), goldCnt) - rank.begin();
    for (int i = 0; i < hr; i++) 
        canGold[i] = 1;
    if (min(35, (okTeam + 10) / 10) > goldCnt) {
        int id = -1, rk = -1;
        for (int i = 0; i < teamCnt; i++) {
            if (teams[i].score >= 1) 
                continue;
            auto getTeam = teams[i];
            getTeam.becomeAC();
            int getRank = lower_bound(all(teams), getTeam) - teams.begin();
            if (getTeam.score >= 1 && rk < getRank) {
                id = i;
                rk = getRank;
            }
        }
        if (id != -1) {
            auto getTeam = teams[id];
            getTeam.becomeAC();
            for (int i = 0; i < teamCnt; i++) {
                int newRank = rank[i] - (teams[id] < teams[i]) + (getTeam < teams[i]);
                if (newRank < min(35, (okTeam + 10) / 10)) 
                    canGold[i] = 1;
            }
        }
    }
    for (int i = 0; i < goldCnt; i++) {
        auto getTeam = teams[i];
        getTeam.becomeWeak();
        int newOkTeam = okTeam - (teams[i].score >= 1) + (getTeam.score >= 1);
        int newGoldCnt = min(35, (newOkTeam + 9) / 10);
        for (int j = hr; j < teamCnt; j++) {
            int newRank = rank[j] - (teams[i] < teams[j]) + (getTeam < teams[j]);
            if (newRank < newGoldCnt) 
                canGold[j] = 1;
        }
    }
    for (int i = hr; i < teamCnt; i++) {
        if (canGold[i]) 
            continue;
        auto getTeam = teams[i];
        getTeam.becomeStronger();
        int newOkTeam = okTeam - (teams[i].score >= 1) + (getTeam.score >= 1);
        int newGoldCnt = min(35, (newOkTeam + 9) / 10);
        int newRank = lower_bound(all(teams), getTeam) - teams.begin();
        if (newRank < newGoldCnt) 
            canGold[i] = 1;
    }
    VI ans;
    for (int i = 0; i < teamCnt; i++) 
        if (canGold[i]) 
            ans.pb(i);
    printf("%d\n", SZ(ans));
    for (auto i : ans) 
        cout << names[teams[i].id] << " ";
    puts("");
}

int main() {
    scanf("%d", &TC);
    while (TC--) {
        solve();
    }
}

Comments

avatar
tzl_Dedicatus545
唐。
  • 2026-02-11 14:34:23