QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605259#8230. SubmissionsDBsoleil#WA 4ms13028kbC++204.1kb2024-10-02 16:25:532024-10-02 16:25:56

Judging History

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

  • [2024-10-02 16:25:56]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:13028kb
  • [2024-10-02 16:25:53]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e5 + 5;
int n, m, tn, hn, tn1, sn, a[Maxn];
bool ans[Maxn];
map<string, int> ind;
string name[Maxn];
vector<pair<int, int>> v[Maxn][27], V[27];
int sum[Maxn], csum[Maxn][27], pend[Maxn], rsum, rcsum[27], rpend;
pair<int, int> grade[Maxn], rgrade[Maxn], tgrade[Maxn];
int get(const string &x) {
  if (ind.find(x) == ind.end()) {
    int t = (int)ind.size() + 1;
    name[t] = x, ind[x] = t;
  } return ind[x];
} // get
bool compare(pair<int, int> lhs, pair<int, int> rhs) {
  return lhs.first > rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
} // compare
void calc(vector<pair<int, int>> *v, int &s, int c[], int &p) {
  s = p = 0;
  for (int j = 1; j <= 26; ++j) {
    int cur_pend = 0; c[j] = 0;
    for (const auto &[t, mn]: v[j]) {
      // fprintf(stderr, "j = %d, (t, mn) = (%d, %d)\n", j, t, mn);
      if (c[j] == 0) {
        if (t == 0) cur_pend += 20;
        else cur_pend += mn;
      }
      c[j] += t;
    }
    s += (c[j] > 0);
    if (c[j] > 0) p += cur_pend;
  }
} // calc
int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tests; cin >> tests;
  while (tests--) {
    ind.clear();
    cin >> m;
    for (int i = 0; i < m; ++i) {
      string nm, ts, p; int mn;
      cin >> nm >> ts >> mn >> p;
      int j = get(nm), t = ts[0] - 'A' + 1;
      v[j][t].emplace_back(p == "accepted", mn);
    }
    n = (int)ind.size(); hn = 0;
    for (int i = 1; i <= n; ++i) {
      calc(v[i], sum[i], csum[i], pend[i]);
      grade[i] = {sum[i], pend[i]};
      // fprintf(stderr, "grade[%d] = {%d, %d}\n", i, sum[i], pend[i]);
    }
    for (int i = 1; i <= n; ++i) hn += (sum[i] > 0);
    tn = min((hn + 9) / 10, 35); sn = tn;
    for (int i = 1; i <= n; ++i) a[i] = i;
    sort(a + 1, a + n + 1, [&](int x, int y)->bool {
        return compare(grade[x], grade[y]); });
    while (sn + 1 <= n && grade[a[sn + 1]] == grade[a[sn]]) ++sn;
    // fprintf(stderr, "sn = %d\n", sn);
    // for (int i = 1; i <= n; ++i) fprintf(stderr, "a[%d] = %d\n", i, a[i]);
    fill(ans + 1, ans + n + 1, false);
    for (int i = 1; i <= sn; ++i) ans[a[i]] = true;
    for (int i = tn + 1; i <= n; ++i) {
      for (int j = 1; j <= 26; ++j) if (!v[a[i]][j].empty()) {
        for (int k = 1; k <= 26; ++k) V[k] = v[a[i]][k];
        for (auto &[p, mn]: V[j]) if (p == 0) { p = 1; break; }
        calc(V, rsum, rcsum, rpend);
        pair<int, int> rgrade = {rsum, rpend};
        // if (i == 3) fprintf(stderr, "rgrade = {%d, %d}\n", rsum, rpend);
        int hn1 = hn + (rsum != 0 && sum[a[i]] == 0);
        int tn1 = min(35, (hn1 + 9) / 10);
        // fprintf(stderr, "hn1 = %d, tn1 = %d\n", hn1, tn1);
        if (compare(rgrade, grade[a[tn1]]) || rgrade == grade[a[tn1]]) { ans[a[i]] = true; break; }
      }
    }
    if (sn == tn) {
      for (int i = 1; i <= tn; ++i) {
        for (int j = 1; j <= 26; ++j) if (!v[a[i]][j].empty()) {
          for (int k = 1; k <= 26; ++k) V[k] = v[a[i]][k];
          for (auto &[p, mn]: V[j]) if (p == 1) { p = 0; break; }
          calc(V, rsum, rcsum, rpend);
          pair<int, int> rgrade = {rsum, rpend};
          if (compare(grade[a[tn + 1]], rgrade)) { ans[a[tn + 1]] = true; break; }
        }
        if (ans[a[tn + 1]]) break;
      }
      if (sum[a[n]] == 0) {
        tn1 = min(hn / 10 + 1, 35);
        if (tn1 != tn) {
          int sn1 = tn1;
          while (sn1 + 1 <= n && grade[a[sn1]] == grade[a[sn1 + 1]]) ++sn1;
          for (int i = 1; i <= sn1; ++i) ans[a[i]] = true;
          ans[a[tn1]] = true;
        }
      }
    }

    int nans = accumulate(ans + 1, ans + n + 1, 0);
    cout << nans << endl;
    vector<string> sans;
    for (int i = 1; i <= n; ++i)
      if (ans[i]) sans.push_back(name[i]);
    for (int i = 0; i < (int)sans.size(); ++i)
      cout << sans[i] << " \n"[i == (int)sans.size() - 1];
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= 26; ++j)
        v[i][j].clear(), csum[i][j] = 0;
    for (int i = 1; i <= n; ++i) sum[i] = pend[i] = 0;
  }
  return 0;
} // main

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 10228kb

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

result:

ok 2 test cases ok. (2 test cases)

Test #2:

score: 0
Accepted
time: 4ms
memory: 10292kb

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: 4ms
memory: 9144kb

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

result:

ok 2 test cases ok. (2 test cases)

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 13028kb

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:

3
A B C
11
A K B C D E F G H I J

result:

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