QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647114#8230. SubmissionsAlphaZeWA 13ms72080kbC++205.3kb2024-10-17 11:48:332024-10-17 11:48:33

Judging History

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

  • [2024-10-17 11:48:33]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:72080kb
  • [2024-10-17 11:48:33]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define x first
#define y second

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f = ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

const int M = 1e5 + 10, N = 25, inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7, p = 13331;
int m; 
int penal[26];
bool ans[M];
int n;
struct Submit {
    int t, s;
};
struct Grade {
    int nm, t;
    void clear() { nm = t = 0; }
    bool operator < (const Grade &that) const {
        if (nm == that.nm) return t < that.t;
        return nm > that.nm;
    }
    bool operator == (const Grade &that) const {
        return nm == that.nm && t == that.t;
    }
};
struct Team {
    char str[N]; 
    vector<Submit> e[26];
    int ac;
    Grade g1, g2, g3, g4;
    
    void ins() {

        g1.clear(); memset(penal, 0, sizeof penal);
        // puts("sb?1");
        for (int i = 0; i < 26; ++i) {
            if (ac >> i & 1) {
                ++g1.nm; // puts("sb?");
                for (auto sub : e[i]) {
                    if (sub.s) {
                        g1.t += sub.t, penal[i] += sub.t;
                        break;
                    } else g1.t += 20, penal[i] += 20;
                }
            }
        } // 初始成绩
        
        g2 = g1;
        for (int i = 0; i < 26; ++i) {
            if (!(ac >> i & 1)) {
                if (!e[i].empty()) {
                    Grade nowg = {g1.nm + 1, g1.t + e[i][0].t};
                    g2 = min(g2, nowg);
                }
            } else {
                Grade nowg = {g1.nm, g1.t - penal[i] + e[i][0].t};
                g2 = min(g2, nowg);
            }
        } // 改一个成绩后最优

        g3 = g4 = g2;
        for (int i = 0; i < 26; ++i) {
            if (ac >> i & 1) {
                int nowpenal = 0, times = 0;
                for (auto sub : e[i]) {
                    if (!sub.s) nowpenal += 20;
                    else {
                        if (!times) {
                            nowpenal += 20; ++times;
                        } else {
                            nowpenal += sub.t; ++times; break;
                        }
                    }
                }
                if (times == 1) g3 = max(g3, {g1.nm - 1, g1.t - penal[i]});
                else g4 = max(g4, {g1.nm, g1.t - penal[i] + nowpenal});
            }
        }
    }
    bool operator < (const Team &that) const {
        if (g1 == that.g1) return max(that.g3, that.g4) < max(g3, g4);
        return g1 < that.g1;
    }
}nd[M];

int getgold(int x) {
    if (x % 10 == 0) return min(x / 10, 35);
    return min(x / 10 + 1, 35);
}

void work() {
    m = read(); n = 0; map<ll, int> mp; 
    for (int i = 1; i <= m; ++i) {
        char str[N];
        scanf("%s", str + 1);
        int len = strlen(str + 1); ll has = 0;
        for (int j = 1; j <= len; ++j) has = (has * p + str[j]) % mod;
        if (mp.find(has) == mp.end()) {
            mp[has] = ++n; 
            for (int j = 1; j < N; ++j) nd[n].str[j] = str[j];
            for (int j = 0; j < 26; ++j) nd[n].e[j].clear(); nd[n].ac = 0;
        }
        int idx = mp[has];
        char problem = getchar();
        while (problem < 'A' || problem > 'Z') problem = getchar();
        int t = read();
        char status = getchar();
        while (status != 'r' && status != 'a') status = getchar();
        int p = problem - 'A', s = status == 'a';
        if (s == 1) nd[idx].ac |= 1 << p;
        nd[idx].e[p].push_back({t, s});
        // printf("nd[%d].e[%d].pb({%d, %d}); \n", idx, p, t, s);
        while (status != '\n') status = getchar();
    }
    for (int i = 1; i <= n; ++i) {
        nd[i].ins();
        // printf("%s\n", nd[i].str + 1);
        // printf("{%d, %d}, {%d, %d}, {%d, %d}, {%d, %d}; \n", nd[i].g1.nm, nd[i].g1.t, nd[i].g2.nm, nd[i].g2.t, nd[i].g3.nm, nd[i].g3.t, nd[i].g4.nm, nd[i].g4.t);
    }
    sort(nd + 1, nd + n + 1);
    int nn = n;
    for (int i = nn; i; --i) 
        if (!nd[i].g1.nm) nn = i - 1;
        else break;
    int gold = getgold(nn);
    for (int i = 1; i <= n; ++i) ans[i] = 0;
    for (int i = 1; i <= gold; ++i) ans[i] = 1;
    for (int i = gold + 1; i <= n; ++i) {
        int nown = nn + (nd[i].g1.nm == 0), nowgold = getgold(nown);
        if (nd[i].g2 < nd[nowgold].g1 || nd[i].g2 == nd[nowgold].g1) ans[i] = 1;
    }
    bool tag = 0;
    if (getgold(nn) != getgold(nn - 1)) tag = 1;
    Grade tog = nd[1].g4; int id = 1;
    for (int i = 1; i <= gold; ++i) {
        Grade nowtog = nd[1].g4;
        if (nd[1].g3.nm || (!tag)) nowtog = max(nowtog, nd[1].g3);
        if (tog < nowtog) tog = nowtog, id = i;
    }
    tog = min(tog, nd[gold + 1].g1);
    // printf("tog = {%d, %d}; \n", tog.nm, tog.t);
    for (int i = gold + 1; i <= n; ++i) {
        if (nd[i].g1 < tog || nd[i].g1 == tog) ans[i] = 1;
    }
    int ansnm = 0;
    for (int i = 1; i <= n; ++i) ansnm += ans[i];
    printf("%d\n", ansnm);
    for (int i = 1; i <= n; ++i)
        if (ans[i]) printf("%s ", nd[i].str + 1); putchar('\n');
}

int main() {
    int Tt = read();
    while (Tt--) work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 71800kb

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
LetItRot XuejunXinyoudui1 AllWayTheNorth ImYourFan 

result:

ok 2 test cases ok. (2 test cases)

Test #2:

score: 0
Accepted
time: 3ms
memory: 72080kb

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: -100
Wrong Answer
time: 6ms
memory: 71784kb

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:

2
A K 
1
A 

result:

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