QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485715 | #8230. Submissions | Swarthmore | WA | 91ms | 3904kb | C++20 | 6.1kb | 2024-07-21 02:23:48 | 2024-07-21 02:23:48 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
const char nl = '\n';
// Increase:
// - Change problem to earliest success (could increase n)
// - Make another decrease rank (precompute)
// - Increase n (# that solve > 0 problems (everyone has at least 1 attempt))
// - Should increase lowest one
// - If currently have 0, could increase n simultaneously
// Decrease:
// - Change problem from earliest success to fail
// - This either decreases total (could decrease n)
// - Or increases penalty
struct Score {
int score, penalty;
bool operator<(const Score& o) const {
if (score != o.score) return score > o.score;
return penalty < o.penalty;
}
};
Score operator+(Score a, Score b) {
return {a.score + b.score, a.penalty + b.penalty};
}
void solve() {
int M; cin >> M;
map<string, map<string, vector<pair<int, bool>>>> mp;
while (M--) {
string team; cin >> team;
string prob; cin >> prob;
int t; cin >> t;
string s; cin >> s;
bool p = s == "accepted";
mp[team][prob].push_back({t, p});
}
int n = 0;
vector<pair<Score, string>> scores;
map<string, Score> toScore;
vector<pair<Score, string>> newZeroScores;
for (const auto& [team, m]: mp) {
int num = 0;
int penalty = 0;
for (auto [_, v]: m) {
bool got = false;
int add = 0;
int num_fail = 0;
for (auto [t, s]: v) {
if (s) {
got = true;
add += t;
add += 20 * num_fail;
break;
}
else {
num_fail++;
}
}
if (got) {
num++;
penalty += add;
}
}
if (num > 0) n++;
scores.push_back({{num, penalty}, team});
toScore[team] = {num, penalty};
// cout << team << ": " << num << ' ' << penalty << endl;
// if have zero, add to zero scores
if (num == 0) {
int maxPenalty = 0;
for (auto [_, v]: m) {
maxPenalty = max(maxPenalty, v.back().first + 20 * (sz(v) - 1));
}
newZeroScores.push_back({{1, maxPenalty}, team});
}
}
sort(all(scores));
sort(all(newZeroScores));
map<string, int> teamToIndex;
for (int i = 0; i < sz(scores); i++) {
teamToIndex[scores[i].second] = i;
}
vector<Score> justScores;
for (auto [s, _]: scores) justScores.push_back(s);
auto getr = [&](Score s) -> int {
auto it = std::lower_bound(all(justScores), s);
return distance(justScores.begin(), it);
};
int target = min((n + 9) / 10, 35);
int new_target = min((n + 1 + 9) / 10, 35);
int new_target_sub = min((n - 1 + 9) / 10, 35);
// cout << target << ' ' << new_target << ' ' << new_target_sub << nl;
vector<int> pfx(sz(scores) + 1);
// get decrease scores
for (int i = 0; i < sz(scores); i++) {
auto [score, team] = scores[i];
auto [num, penalty] = score;
for (auto [_, v]: mp[team]) {
int num_fail = 0;
vector<int> accepts;
for (auto [t, s]: v) {
if (s) {
accepts.push_back(t + 20 * num_fail);
num_fail++;
// don't break
}
else {
num_fail++;
}
}
int newScore = num, newPenalty = penalty;
if (sz(accepts) > 0) {
if (sz(accepts) == 1) {
newScore--;
newPenalty -= accepts[0];
}
else {
// take next accept instead
newPenalty = penalty - accepts[0] + accepts[1];
}
// only consider if doesn't decrease target
if (newScore > 0 || new_target_sub == target) {
// cout << "consider: " << team << ' ' << newScore << ' ' << newPenalty << endl;
int ii = distance(justScores.begin(), upper_bound(all(justScores), score));
int j = getr({newScore, newPenalty});
// [ii, j)
if (ii < j) {
pfx[ii]++;
pfx[j]--;
}
}
}
}
}
FOR(i, 1, sz(pfx)) {
pfx[i] += pfx[i-1];
}
// cout << "target: " << target << ' ' << n << nl;
map<string, int> canWin;
for (const auto& [team, m]: mp) {
auto [score, penalty] = toScore[team];
canWin[team] = getr(toScore[team]) < target;
for (auto [_, v]: m) {
bool got = false;
int add = 0;
int num_fail = 0;
for (auto [t, s]: v) {
if (s) {
got = true;
add += t;
add += 20 * num_fail;
break;
}
else {
num_fail++;
}
}
int newScore = score, newPenalty = penalty;
if (got) {
newPenalty = penalty - add + v[0].first;
}
else {
newScore++;
newPenalty += v[0].first;
}
if (score == 0 && newScore > 0) {
canWin[team] |= getr({newScore, newPenalty}) < new_target;
}
else {
canWin[team] |= getr({newScore, newPenalty}) < target;
}
}
// increase somebody else from 0
for (int i = max(0, sz(newZeroScores) - 2); i < sz(newZeroScores); i++) {
auto [zScore, zTeam] = newZeroScores[i];
if (team != zTeam && !(zScore < toScore[team])) {
// if (team != zTeam && toScore[team] < zScore) {
canWin[team] |= getr({score, penalty}) < new_target;
}
}
// check if we can decreasing other rank
if (pfx[teamToIndex[team]] > 0) {
canWin[team] |= getr(toScore[team]) - 1 < target;
}
}
vector<string> wins;
for (auto [team, w]: canWin) {
if (w) wins.push_back(team);
}
cout << sz(wins) << nl;
for (auto s: wins) cout << s << ' ';
cout << nl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while (T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 0ms
memory: 3852kb
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: 0ms
memory: 3836kb
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: 0ms
memory: 3692kb
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: 80ms
memory: 3904kb
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: 91ms
memory: 3628kb
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 845. (test case 845)