QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #756718 | #8230. Submissions | RWeakest | WA | 51ms | 22956kb | C++20 | 8.7kb | 2024-11-16 21:41:31 | 2024-11-16 21:41:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 100;
ll T, n, havepass, m;
string name[N];
string str, state;
ll temp;
char pi;
struct node {
ll ti, p;
bool st;
node(ll ti_ = 0, ll p_ = 0, bool st_ = false) {
ti = ti_, p = p_, st = st_;
}
};
struct score {
ll no, num, sum_ti;
score(ll no_ = 0, ll num_ = 0, ll sum_ti_ = 0) {
no = no_, num = num_, sum_ti = sum_ti_;
}
};
score team[N];
bool cmp(score s1, score s2) {
if (s1.num != s2.num) return s1.num > s2.num;
return s1.sum_ti < s2.sum_ti;
}
bool better(score s1, score s2) {
if (s1.num != s2.num) return s1.num > s2.num;
return s1.sum_ti <= s2.sum_ti;
}
vector<node> tj[N][30];
ll first[N][30], pena[N], passed[N], wrong[N][30];
bool can[N];
score zuicha(int p) {
int pen = pena[p], pas = passed[p];
score badest = score(p, pas, pen);
for (int i = 0; i < 26; i++) {
for (int j = 0; j < tj[p][i].size(); j++) {
if (tj[p][i][j].st) {
int nxttime = -1;
for (int l = j + 1; l < tj[p][i].size(); l++) {
if (tj[p][i][l].st) {
nxttime = tj[p][i][l].ti;
break;
}
}
score chi;
if (nxttime == -1) {
chi = score(p, pas - 1, pen - first[p][i]);
} else {
chi = score(p, pas, pen - first[p][i] + nxttime);
}
if (better(badest, chi)) badest = chi;
break;
}
}
}
return badest;
}
score zuihao(int p) {
int pen = pena[p], pas = passed[p];
score goodest = score(p, pas, pen);
for (int i = 0; i < 26; i++) {
for (int j = 0; j < tj[p][i].size(); j++) {
if (!tj[p][i][j].st) {
score chi;
if (first[p][i] == -1) {
chi = score(p, pen + 1, pas + tj[p][i][j].ti);
} else {
chi = score(p, pen, pas - first[p][i] + tj[p][i][j].ti);
}
if (better(chi, goodest)) goodest = chi;
break;
}
}
}
return goodest;
}
score just(int p) {
score jus = score(p, 2e5, 2e5);
for (int i = 0; i < 26; i++) {
for (auto j: tj[p][i]) {
score chi = score(p, 1, j.ti);
if (better(jus, chi)) jus = chi;
}
}
return jus;
}
void solve() {
cin >> m;
n = 0, havepass = 0;
map<string, int> mp;
mp.clear();
for (int i = 1; i <= m; i++) {
cin >> str >> pi >> temp >> state;
if (!mp[str]) {
n++;
mp[str] = n;
name[n] = str;
}
bool nowst = false;
if (state[0] == 'a') nowst = true;
tj[mp[str]][pi - 'A'].emplace_back(temp, pi - 'A', nowst);
}
//begin
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++)
first[i][j] = -1, wrong[i][j] = 0;
pena[i] = passed[i] = 0;
can[i] = false;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) {
for (auto l: tj[i][j]) {
if (!l.st) wrong[i][j]++;
else if (first[i][j] == -1) {
first[i][j] = l.ti;
passed[i]++;
pena[i] += l.ti;
pena[i] += wrong[i][j] * 20;
}
}
}
if (passed[i] > 0) havepass++;
team[i] = score(i, passed[i], pena[i]);
}
sort(team + 1, team + 1 + n, cmp);
//gold_num
ll goldnum = min(ceil(0.1 * havepass), 35.0);
ll gdp = goldnum;
while (gdp < n && team[gdp + 1].num == team[gdp].num && team[gdp + 1].sum_ti == team[gdp].sum_ti) gdp++;
for (int i = 1; i <= gdp; i++) can[team[i].no] = true;
//test_out
// cout << gdp << " gdp\n";
// for (int i = 1; i <= n; i++) {
// printf("team:%d %s num:%lld pena:%lld\n", i, name[team[i].no].c_str(), team[i].num, team[i].sum_ti);
// for (int j = 0; j < 26; j++) {
// for (auto l: tj[i][j]) {
// printf("p:%lld ti:%lld st:%d\n", l.p, l.ti, l.st);
// }
// }
// }
//silver_first
if (gdp == goldnum && gdp != n) {
bool can_s_f_1 = false, can_s_f_2 = false;
//havepass++
score worst1 = score(1, 2e5, 2e5);
if (min(ceil(0.1 * (havepass + 1ll)), 35.0) > gdp) {
// printf("havr pass may ++\n");
for (int i = gdp + 1; i <= n; i++) {
if (passed[team[i].no] == 0) {
score best = just(team[i].no);
if (best.num > 0) {
can_s_f_1 = true;
if (better(worst1, best))
worst1 = best;
}
}
}
}
bool maydec = false;
if (min(ceil(0.1 * (havepass - 1)), 35.0) < gdp)
maydec = true;
for (int i = 1; i <= gdp; i++) {
score worst = zuicha(team[i].no);
if (better(team[gdp + 1], worst) && (worst.num != 0 || !maydec)) can_s_f_2 = true;
}
// printf("can_s_f %d %d\n", can_s_f_1, can_s_f_2);
if (can_s_f_1) {
for (int i = gdp + 1; i <= n; i++) {
if (team[i].num == 0 && better(zuihao(team[i].no), worst1)) can[team[i].no] = true;
}
// printf("worst1 %lld %lld %lld\n", worst1.no, worst1.num, worst1.sum_ti);
if (better(team[gdp + 1], worst1)) {
// printf("can s_f_1\n");
int nowp = gdp + 1;
can[team[gdp + 1].no] = true;
while (nowp < n && better(team[nowp + 1], team[nowp])) {
nowp++;
can[team[nowp].no] = true;
}
}
}
if (can_s_f_2) {
int nowp = gdp + 1;
can[team[gdp + 1].no] = true;
while (nowp < n && better(team[nowp + 1], team[nowp])) {
nowp++;
can[team[nowp].no] = true;
}
for (int i = nowp + 1; i <= n; i++) {
if (team[i].num == 0 && better(zuihao(team[i].no), team[nowp])) can[team[i].no] = true;
}
}
}
//not_gold
for (int i = gdp + 1; i <= n; i++) {
if (better(zuihao(team[i].no), team[gdp])) can[team[i].no] = true;
}
//output
ll allcan = 0;
for (int i = 1; i <= n; i++) if (can[i]) allcan++;
cout << allcan << "\n";
for (int i = 1; i <= n; i++) if (can[i]) cout << name[i] << " ";
cout << "\n";
//clear
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) {
tj[i][j].clear();
}
}
mp.clear();
for (int i = 1; i <= n; i++) can[i] = false;
for (int i = 1; i <= n; i++) team[i] = score(0, 0, 0);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
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 accepted
ImYourFan I 257 accepted
ImYourFan Y 257 accepted
AllWayTheNorth T 264 accepted
XuejunXinyoudui1 J 294 accepted
LetItRot I 299 accepted
LetItRot I 299 rejected
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
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 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 rejected
K K 2 rejected
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 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 20756kb
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: 4ms
memory: 22784kb
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: 8ms
memory: 19312kb
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: 4ms
memory: 22956kb
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: 51ms
memory: 22552kb
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: 41ms
memory: 22352kb
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:
8 FVJL tsd Qua1Pti3vKhyQKDUm xx2yiu6x fYuK1KNkuyO5HRCq H7Eb0AZyC9qWoY l5ClvOhvY_DEMrXu xiLm0TUOF3T 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 pVWDEz 3BQ 2 tg buCeoOotAkV8DaFD6 3 5YXaq98F7gfWOYrs77bQ UkXQ3iaNJ APV52YY98srBBt 4 5 oCZu7dczuj43 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo w...
result:
wrong answer the numbers are different in the case 1. (test case 1)