QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #641122 | #8230. Submissions | Tomorrow | WA | 82ms | 3820kb | C++17 | 2.7kb | 2024-10-14 18:37:56 | 2024-10-14 18:37:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define C const
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define TTT template<typename T = I>
#define BE(v) v.begin(), v.end()
#define VD void
#define I int
#define STR string
using PII = pair<I, I>;
TTT using V = vector<T>;
#define FORX(v) for(auto& x : v)
#define FOR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }
VD test()
{
I n = 0, m; cin >> m;
unordered_map<STR, I> ns;
V<STR> tn;
V<V<V<I>>> tm;
FOR(i, 0, m)
{
STR nm, pl, st; I t; cin >> nm >> pl >> t >> st;
if (!ns.count(nm))ns[nm] = n++, tn.pb(nm), tm.pb(V<V<I>>(26));
tm[ns[nm]][pl[0] - 'A'].pb(st == "accepted" ? ~t : t);
}
FUNC(V<PII>, calc, V<I>&v, PII & s)//s = { 0,0 };
{
I n = v.size(), fa = -1;
V<PII> res(n);
FORR(i, n - 1, -1)if (v[i] < 0)res[i] = s, s = { -1,i * 20 + ~v[i] }, fa = i;
FOR(i, 0, n)
{
if (v[i] < 0 && i != fa)res[i] = s;
if (v[i] >= 0)res[i] = min(s, { -1,i * 20 + ~v[i] });
}
return res;
};
V<PII> sc(n); V<V<PII>> dlt(n);
FOR(i, 0, n)
{
FOR(j, 0, 26)
{
PII b; V<PII> r = calc(tm[i][j], b);
sc[i].ft += b.ft, sc[i].sd += b.sd;
FORX(r)dlt[i].pb({ x.ft - b.ft,x.sd - b.sd });
}
}
I sn = 0;
FOR(i, 0, n)if (sc[i].ft < 0)++sn;
V<I> rk(n), vs(n);
V<PII> ss(sc); sort(BE(ss));
FOR(i, 0, n)rk[i] = lower_bound(BE(ss), sc[i]) - ss.begin();
PII lgs = { -100 ,-1e9 };
FOR(i, 0, n)
{
if (rk[i] < min((int)ceil(sn * 0.1), 35))vs[i] = 1;
FOR(j, 0, dlt[i].size())
{
PII ns = dlt[i][j];
ns.ft += sc[i].ft, ns.sd += sc[i].sd;
I nsn = sn;
if (sc[i].ft == 0 && ns.ft < 0)++nsn;
if (sc[i].ft < 0 && ns.ft == 0)--nsn;
I gn = min((int)ceil(nsn * 0.1), 35);
I nr = lower_bound(BE(ss), ns) - ss.begin();
if (nr > rk[i])--nr;
if (nr < gn)vs[i] = 1;
if (gn == 0)continue;
V<PII> g;
FOR(k, 0, min(40, n))if (rk[i] != k)g.pb(ss[k]);
g.pb(ns);
sort(BE(g));
setmax(lgs, g[gn - 1]);
}
}
FOR(i, 0, n)if (sc[i] <= lgs)vs[i] = 1;
I ans = 0;
FOR(i, 0, n)if (vs[i])++ans;
cout << ans << '\n';
FOR(i, 0, n)if (vs[i])cout << tn[i] << ' ';
cout << '\n';
}
I main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if (fopen("test.in", "r"))
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}
I t = 1;
cin >> t;
while (t--)test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 0ms
memory: 3556kb
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: 3608kb
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: 0ms
memory: 3784kb
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: 82ms
memory: 3560kb
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: 64ms
memory: 3588kb
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 4 ldaKLZb1oS1sS _Yej1PrINtydmOudwo...
result:
wrong answer the numbers are different in the case 12. (test case 12)