QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #328793 | #8230. Submissions | yan_silva | WA | 1ms | 3640kb | C++20 | 3.4kb | 2024-02-16 06:43:48 | 2024-02-16 06:43:48 |
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;
set<string> names;
vector<tuple<string, int, int, bool>> ev;
for (int i = 0; i < n; i++) {
string c, s; char p; int t;
cin>>c>>p>>t>>s;
names.insert(c);
ev.emplace_back(c, p-'A', t, s == "accepted");
}
int id = 0;
map<string, int> to;
vector<string> inv(names.size());
for (auto name: names) {
inv[id] = name;
to[name] = id++;
}
vector<vector<vector<int>>> ac(id, vector<vector<int>>(26)),
wa(id, vector<vector<int>>(26));
for (int i = 0; i < n; i++) {
auto [c, p, t, is_ac] = ev[i];
if (is_ac) {
ac[to[c]][p].push_back(i);
} else {
wa[to[c]][p].push_back(i);
}
}
auto get_penalty = [&](int i, char c, int t) {
int lb = lower_bound(all(wa[i][c]), t) - wa[i][c].begin();
return get<2>(ev[t]) + lb*20;
};
int sz = 0;
vector<pair<int,int>> val(id);
set<tuple<int, int, int>> teams;
for (int i = 0; i < id; i++) {
int num = 0, time = 0;
for (int j = 0; j < 26; j++) {
if (ac[i][j].size()) {
num++;
time += get_penalty(i, j, ac[i][j][0]);
}
}
val[i] = {-num, time};
teams.emplace(-num, time, i);
if (num) sz++;
}
auto get_top_size = [&sz]() {
return min(35LL, (sz+9)/10);
};
vector<bool> res(id);
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[c] = true;
top--;
prv_num = num, prv_time = time;
}
};
update();
for (int i = 0; i < n; i++) {
auto [c, p, t, is_ac] = ev[i];
int cur = to[c];
auto [num, time] = val[cur];
int sv_sz = sz, new_num = -num, new_time = time;
bool valid = false;
if (is_ac) {
if (ac[cur][p][0] == i) {
valid = true;
if (ac[cur][p].size() > 1) {
new_time = new_time - get_penalty(cur, p, i) + get_penalty(cur, p, ac[cur][p][1]) + 20;
} else {
// nao tenho mais ac na questao atual
new_num--;
new_time = new_time - get_penalty(cur, p, i);
if (new_num == 0) sz--;
}
}
} else {
if (ac[cur][p].size()) {
// ja tinha ac na questao
// se o ac for depois
// entao quero remover a penalidade dele
// e adicionar a do atual
if (i < ac[cur][p][0]) {
valid = true;
new_time = new_time - get_penalty(cur, p, ac[cur][p][0]) + get_penalty(cur, p, i);
}
} else if (i == wa[cur][p][0]) {
// nao tinha nenhum ac
new_num++;
new_time = new_time + get_penalty(cur, p, i);
if (new_num == 1) sz++;
valid = true;
}
}
if (valid) {
teams.erase({num, time, cur});
teams.insert({-new_num, new_time, cur});
update();
teams.erase({-new_num, new_time, cur});
teams.insert({num, time, cur});
}
sz = sv_sz;
}
int cnt = 0;
for (int i = 0; i < id; i++) {
if (res[i]) cnt++;
}
cout<<cnt<<'\n';
for (int i = 0; i < id; i++) {
if (res[i]) cout<<inv[i]<<' ';
}
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: 3628kb
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: 3608kb
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: -100
Wrong Answer
time: 0ms
memory: 3640kb
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)