QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #328769 | #8230. Submissions | yan_silva | WA | 146ms | 3956kb | C++20 | 2.8kb | 2024-02-16 06:17:09 | 2024-02-16 06:17:10 |
Judging History
answer
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
using ll = long long;
#define int ll
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
void solve() {
int n; cin>>n;
map<string, vector<vector<int>>> ac, wa;
vector<tuple<string, int, int, string>> ev;
for (int i = 0; i < n; i++) {
string c, s; char p; int t;
cin>>c>>p>>t>>s;
if (!ac.count(c)) {
ac[c].resize(26);
wa[c].resize(26);
}
if (s == "accepted") {
ac[c][p-'A'].push_back(i);
} else {
wa[c][p-'A'].push_back(i);
}
ev.emplace_back(c, p-'A', t, s);
}
auto get_penalty = [&](string s, char c, int t) {
int lb = lower_bound(all(wa[s][c]), t) - wa[s][c].begin();
return get<2>(ev[t]) + lb*20;
};
int sz = 0;
map<string, pair<int,int>> val;
multiset<tuple<int, int, string>> teams;
for (auto [c, v]: ac) {
int num = 0, time = 0;
for (int i = 0; i < 26; i++) {
if (v[i].size()) {
num++;
time += get_penalty(c, i, v[i][0]);
}
}
val[c] = {-num, time};
teams.emplace(-num, time, c);
if (num) sz++;
}
auto get_top_size = [&sz]() {
return min(35LL, (sz+9)/10);
};
set<string> res;
auto update = [&]() {
int top = get_top_size(), prv_num = 1, prv_time = 1;
for (auto [num, time, c]: teams) {
if (top <= 0) {
if (num != prv_num or time != prv_time) break;
}
res.insert(c);
top--;
prv_num = num, prv_time = time;
}
};
update();
for (int i = 0; i < n; i++) {
auto [c, p, t, s] = ev[i];
auto [num, time] = val[c];
teams.erase({num, time, c});
int sv_sz = sz, new_num = -num, new_time = time;
if (s == "accepted") {
if (ac[c][p].size() > 1) {
new_time = new_time - get_penalty(c, p, ac[c][p][0]) + get_penalty(c, p, ac[c][p][1]);
} else {
// nao tenho mais ac na questao atual
new_num--;
new_time = new_time - get_penalty(c, p, ac[c][p][0]);
if (new_num == 0) sz--;
}
} else {
if (ac[c][p].size()) {
// ja tinha ac na questao
// se o ac for depois
// entao quero remover a penalidade dele
// e adicionar a do atual
new_time = new_time - get_penalty(c, p, ac[c][p][0]) + get_penalty(c, p, i);
} else {
// nao tinha nenhum ac
new_num++;
new_time = new_time + get_penalty(c, p, i);
if (new_num == 1) sz++;
}
}
teams.insert({-new_num, new_time, c});
update();
teams.erase({-new_num, new_time, c});
teams.insert({num, time, c});
sz = sv_sz;
}
cout<<res.size()<<'\n';
for (auto c: res) cout<<c<<' '; cout<<'\n';
}
signed main() {
fastio;
int tt; cin>>tt;
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
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 AllWayTheNorth ImYourFan LetItRot XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3592kb
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 jiangly_fan 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3604kb
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 B C D E F G H I J K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3668kb
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: 102ms
memory: 3888kb
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: 146ms
memory: 3956kb
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 Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq tsd xiLm0TUOF3T 2 JP t3 2 77sgqpbTIr_Zt1 fhYPGC8W82NwJTQL 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz wJlbqIU 2 6mbCu5zA eiuF7a_ 1 xy6QBr8ECi 3 PezeyUurYoz7N1iGU _Yej1PrINtydmO...
result:
wrong answer the numbers are different in the case 7272. (test case 7272)