QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #359840 | #8230. Submissions | ricofx | WA | 81ms | 7920kb | C++17 | 7.3kb | 2024-03-20 21:46:48 | 2024-03-20 21:46:48 |
Judging History
answer
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define rank miku
#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int N = 1e5 + 5;
int m;
struct submission {
int c;
char p;
int t, ac;
} ss[N];
int tot, fa[N], tr[N][2], sz[N], cnt[N], rt;
pii val[N];
void maintain(int x) {
sz[x] = sz[tr[x][0]] + sz[tr[x][1]] + cnt[x];
}
int getdir(int x) {
return tr[fa[x]][1] == x;
}
void clear(int x) {
fa[x] = sz[x] = cnt[x] = tr[x][0] = tr[x][1] = 0;
val[x] = {0, 0};
}
int create(pii v) {
++tot;
val[tot] = v;
sz[tot] = cnt[tot] = 1;
return tot;
}
void rotate(int x) {
if (x == rt) return;
int y = fa[x], z = fa[y], d = getdir(x);
tr[y][d] = tr[x][d ^ 1];
if (tr[x][d ^ 1]) fa[tr[x][d ^ 1]] = y;
fa[y] = x;
tr[x][d ^ 1] = y;
fa[x] = z;
if (z) tr[z][y == tr[z][1]] = x;
maintain(y);
maintain(x);
}
void splay(int x) {
for (int f = fa[x]; f = fa[x], f; rotate(x)) {
if (fa[f]) rotate(getdir(f) == getdir(x) ? f : x);
}
rt = x;
}
int cmp(pii x, pii y) { // return x > y
return x.fi == y.fi ? x.se > y.se : x.fi < y.fi;
}
void insert(pii v) {
if (!rt) {
rt = create(v);
return;
}
int u = rt, f = 0;
while (true) {
if (val[u] == v) {
cnt[u]++;
maintain(u);
maintain(f);
splay(u);
return;
}
f = u, u = tr[u][cmp(v, val[u])];
if (u == 0) {
int id;
fa[id = create(v)] = f;
tr[f][cmp(v, val[f])] = id;
maintain(f);
splay(id);
return;
}
}
}
int rank(pii v) {
int rk = 0;
int u = rt;
while (u) {
if (val[u] == v) {
rk += sz[tr[u][0]];
splay(u);
return rk + 1;
}
if (cmp(val[u], v)) {
u = tr[u][0];
} else {
rk += sz[tr[u][0]] + cnt[u];
u = tr[u][1];
}
}
return -1;
}
pii kth(int x) {
int u = rt;
while (u) {
if (sz[tr[u][0]] + cnt[u] >= x && sz[tr[u][0]] < x) return val[u];
if (x <= sz[tr[u][0]]) {
u = tr[u][0];
} else {
x -= sz[tr[u][0]] + cnt[u];
u = tr[u][1];
}
}
return u ? val[u] : (pii){-1, -1};
}
pii pre() {
int u = tr[rt][0];
if (!u) return val[rt];
while (true) {
if (tr[u][1] == 0) return splay(u), val[u];
u = tr[u][1];
}
return {233, 233};
}
pii suf() {
int u = tr[rt][1];
if (!u) return val[rt];
while (true) {
if (tr[u][0] == 0) return splay(u), val[u];
u = tr[u][0];
}
return {233, 233};
}
void del(pii v) {
if (rank(v) == -1) return;
if (cnt[rt] > 1) {
cnt[rt]--;
return;
}
if (!tr[rt][1] && !tr[rt][0]) {
clear(rt), rt = 0;
} else if (!tr[rt][0]) {
int x = rt;
rt = tr[x][1];
fa[rt] = 0;
clear(x);
} else if (!tr[rt][1]) {
int x = rt;
rt = tr[x][0];
fa[rt] = 0;
clear(x);
} else {
int cur = rt, y = tr[cur][1];
pre();
tr[rt][1] = y;
fa[y] = rt;
clear(cur);
maintain(rt);
}
}
void MAIN() {
cin >> m;
// 枚举每个提交的状态。维护 有效队伍，对这个队伍快速算出 [题数，罚时]，单个题的罚时
// AC->WA 第一个AC,找第二个。否则没有影响 对每个提交维护，是该题第几次提交，是第几次 AC 提交。再对队伍的某个题维护 ac 的 submitid
// WA->AC 之前有AC,没有影响。没有AC，需要重新记录题数和罚时
map<string, int> pid;
map<char, vector<int>> pac[m + 1], psb[m + 1]; // team, problem
int n = 0, acc = 0;
vector<int> count_sub(m + 1, 0), count_ac(m + 1, 0);
vector<string> dip(m + 1);
string name, sta;
for (int i = 1; i <= m; i++) {
cin >> name >> ss[i].p >> ss[i].t >> sta;
if (!pid.count(name)) pid[name] = ++n, dip[n] = name;
ss[i].c = pid[name];
ss[i].ac = (sta == "accepted");
if (ss[i].ac == 1) pac[ss[i].c][ss[i].p].push_back(i);
psb[ss[i].c][ss[i].p].push_back(i);
count_sub[i] = psb[ss[i].c][ss[i].p].size();
count_ac[i] = pac[ss[i].c][ss[i].p].size();
}
vector<pii> grad(n + 1, {0, 0});
for (int i = 1; i <= n; i++) {
for (auto it : psb[i]) {
int x = 0, y = 0;
for (int sid : it.se) {
if (ss[sid].ac == 1) {
++x; y += ss[sid].t; break;
} else y += 20;
}
if (x == 1) grad[i].fi++, grad[i].se += y;
}
acc += (grad[i].fi >= 1);
}
// 定义一个三元组 [solved, time, tot]
auto get = [&](int x) {
auto old = grad[ss[x].c];
if (ss[x].ac == 0) {
if (!pac[ss[x].c][ss[x].p].empty() && pac[ss[x].c][ss[x].p][0] < x) return old;
if (!pac[ss[x].c][ss[x].p].empty()) {
int y = pac[ss[x].c][ss[x].p][0];
old.se -= (count_sub[y] - 1) * 20 + ss[y].t;
}
++old.fi; old.se += (count_sub[x] - 1) * 20 + ss[x].t;
return old;
}
if (!pac[ss[x].c][ss[x].p].empty() && pac[ss[x].c][ss[x].p][0] < x) return old;
if (pac[ss[x].c][ss[x].p].size() > 1) {
int y = pac[ss[x].c][ss[x].p][1];
old.se -= (count_sub[x] - 1) * 20 + ss[x].t;
old.se += (count_sub[y] - 1) * 20 + ss[y].t;
return old;
}
old.se -= (count_sub[x] - 1) * 20 + ss[x].t;
--old.fi;
return old;
};
for (int i = 0; i <= tot; i++) clear(i);
tot = rt = 0;
vector<int> ans;
map<pii, int> ava;
for (int i = 1; i <= n; i++) insert(grad[i]);
int gold = min(35, (acc + 9) / 10);
for (int i = 1; i <= gold; i++) ava[kth(i)] = 1;
for (int i = 1; i <= m; i++) {
//二分 修改 插入 排名
//快速算出新的状态
auto now = get(i);
//cerr << i << ' ' << ss[i].c << ' ' << now.fi << ' ' << now.se << '\n';
del(grad[ss[i].c]);
insert(now);
int tt = acc;
if (grad[ss[i].c].fi >= 1 && now.fi == 0) tt--;
if (grad[ss[i].c].fi == 0 && now.fi >= 1) tt++;
int gold = min(35, (tt + 9) / 10);
//cerr << "#" << rank(now) << '\n';
if (rank(now) <= gold) ans.push_back(ss[i].c);
for (int i = 1; i <= gold; i++) ava[kth(i)] = 1;
del(now);
insert(grad[ss[i].c]);
}
for (int i = 1; i <= n; i++) if (ava[grad[i]]) ans.push_back(i);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << '\n';
for (int x : ans) cout << dip[x] << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while (T--) MAIN();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5688kb
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: 1ms
memory: 5628kb
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: 1ms
memory: 5568kb
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: 0
Accepted
time: 1ms
memory: 5692kb
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 A B 2 A K
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 66ms
memory: 7920kb
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: 81ms
memory: 5668kb
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 tsd Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 pVWDEz 3BQ 2 tg buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo wJlbqIU 9cy_y_RNRwex8j7224hz 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS _Yej1PrINtydmOudwo...
result:
wrong answer the numbers are different in the case 329. (test case 329)