QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #578526 | #8230. Submissions | allbecomeFF | RE | 376ms | 3824kb | C++20 | 7.4kb | 2024-09-20 19:47:49 | 2024-09-20 19:47:50 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
void solve() {
int m; cin >> m;
unordered_map<string, vector<vector<pair<int, int>>>> mp;
vector<string> teams_name;
int team_count = 0;
while (m --) {
string team_name;
char problem;
int s_time;
string accepted_s;
cin >> team_name >> problem >> s_time >> accepted_s;
if (!mp.count(team_name)) {
teams_name.push_back(team_name);
team_count ++;
mp[team_name] = vector<vector<pair<int, int>>>(26);
}
int problem_id = problem - 'A';
int accepted = (accepted_s == "accepted");
mp[team_name][problem_id].push_back(make_pair(s_time, accepted));
}
for (string team : teams_name) {
for (int i = 0; i < 26; i ++) {
sort(mp[team][i].begin(), mp[team][i].end());
}
}
// vector<pair<int, int>> score; // 第一项为相反数
unordered_map<string, pair<int, int>> best_score, origin_score, dead_score;
int ok_count = 0;
for (string team : teams_name) {
int solve_count = 0, sum_of_time = 0;
vector<int> pre_solve(26), cost_time(26);
for (int i = 0; i < 26; i ++) {
vector<pair<int, int>> arr = mp[team][i];
if (arr.size() > 0) {
int sum = 0;
for (auto pa : arr) {
int ti = pa.first, accept = pa.second;
if (accept) {
sum += ti;
sum_of_time += sum;
solve_count ++;
pre_solve[i] = 1;
cost_time[i] = sum;
break;
}
else {
sum += 20;
}
}
}
}
int new_solve_count = solve_count, new_sum_of_time = sum_of_time;
for (int i = 0; i < 26; i ++) {
vector<pair<int, int>> arr = mp[team][i];
if (arr.size() > 0) {
if (!pre_solve[i]) {
if (new_solve_count == solve_count) {
new_solve_count = solve_count + 1;
new_sum_of_time = 0x3f3f3f3f;
}
new_sum_of_time = min(new_sum_of_time, sum_of_time + arr[0].first);
}
else if (new_solve_count == solve_count) {
new_sum_of_time = min(new_sum_of_time, sum_of_time - cost_time[i] + arr[0].first);
}
}
}
int dead_solve_count = solve_count, dead_sum_of_time = sum_of_time;
for (int i = 0; i < 26; i ++) {
vector<pair<int, int>> arr = mp[team][i];
if (arr.size() > 0) {
if (pre_solve[i]) {
int sum = 0;
int accept_first = 0, accept_second = 0;
for (auto pa : arr) {
int ti = pa.first, accept = pa.second;
if (accept) {
if (!accept_first) {
accept_first = 1;
}
else {
sum += ti;
accept_second = 1;
break;
}
}
else {
sum += 20;
}
}
if (!accept_second) {
if (dead_solve_count == solve_count) {
dead_solve_count = solve_count - 1;
dead_sum_of_time = 0;
}
dead_sum_of_time = max(dead_sum_of_time, sum_of_time - cost_time[i]);
}
else if (dead_solve_count == solve_count) {
dead_sum_of_time = max(dead_sum_of_time, sum_of_time - cost_time[i] + sum);
}
}
}
}
// score.push_back(make_pair(-solve_count, sum_of_time)); // 第一项插负值 从大到小排序
if (solve_count > 0) ok_count ++; // 统计有效队伍
dead_score[team] = make_pair(dead_solve_count, dead_sum_of_time);
origin_score[team] = make_pair(solve_count, sum_of_time);
best_score[team] = make_pair(new_solve_count, new_sum_of_time);
}
vector<string> score = teams_name;
sort(score.begin(), score.end(), [&](auto &a, auto &b) -> bool {
int w1 = origin_score[a].first, c1 = origin_score[a].second;
int w2 = origin_score[b].first, c2 = origin_score[b].second;
return (w1 > w2) || (w1 == w2 && c1 < c2);
});
// cout << " " << gold_rank << endl;
vector<string> winner;
unordered_map<string, bool> is_winner_when_others_dead, is_winner;
// 加分反杀
for (string team : teams_name) {
// team = "B";
if (best_score[team].first == 0) {
continue;
}
int gold_rank = min(35, (ok_count + 9) / 10);
if (origin_score[team].first == 0) {
gold_rank = min(35, (ok_count + 1 + 9) / 10);
}
gold_rank = min(gold_rank, team_count);
pair<int, int> settle = origin_score[score[gold_rank - 1]]; // 金尾
// cout << gold_rank << " ## " << score[gold_rank - 1] << endl;
int p1 = best_score[team].first;
int p2 = best_score[team].second;
int w1 = settle.first;
int w2 = settle.second;
if (p1 > w1 || (p1 == w1 && p2 <= w2)) {
winner.push_back(team);
is_winner[team] = 1;
}
}
// 扣分死
int gold_count = min(min(team_count, 35), (ok_count + 9) / 10);
for (int i = 0; i < gold_count; i ++) {
string team = score[i];
// if (origin_score[team].first == 0) continue;
int gold_rank = min(35, (ok_count + 9) / 10);
if (dead_score[team].first == 0) {
gold_rank = min(35, (ok_count - 1 + 9) / 10);
}
gold_rank = min(gold_rank, team_count);
// pair<int, int> settle0 = origin_score[score[gold_rank - 1]]; // 金尾
// int t1 = settle0.first;
// int t2 = settle0.second;
//
pair<int, int> settle = origin_score[score[gold_rank]]; // 非金首
int p1 = settle.first;
int p2 = settle.second;
int w1 = dead_score[team].first;
int w2 = dead_score[team].second;
// if (w1 > t1 || (w1 == t1 && w2 <= t2)) {
// continue;
// }
//
if (p1 > w1 || (p1 == w1 && p2 <= w2)) {
int tmp_id = gold_rank;
// cout << score[tmp_id] << endl;
if (is_winner_when_others_dead[score[tmp_id]] == 1) {
continue;
}
while (tmp_id < ok_count && origin_score[score[tmp_id]] == settle) {
if (!is_winner[score[tmp_id]]) {
winner.push_back(score[tmp_id]);
is_winner[score[tmp_id]] = 1;
// cout << score[tmp_id] << " ?? ";
}
is_winner_when_others_dead[score[tmp_id]] = 1;
tmp_id ++;
}
}
}
// 额外名额
if (ok_count % 10 == 0) {
int last_time = 0;
for (string team : teams_name) {
if (origin_score[team].first == 0 && best_score[team].first == 1) {
int lastest_time = 0;
for (int i = 0; i < 26; i ++) {
vector<pair<int, int>> arr = mp[team][i];
if (arr.size() > 0) {
int arr_count = arr.size();
int sum = 20 * (arr_count - 1);
sum += arr[arr_count - 1].second;
lastest_time = max(lastest_time, sum);
}
}
last_time = max(last_time, lastest_time);
}
}
int gold_extra = ok_count / 10 + 1;
gold_extra = min(gold_extra, team_count);
pair<int, int> settle = origin_score[score[gold_extra - 1]];
if (settle.second < last_time) {
int tmp_id = gold_extra - 1;
while (tmp_id < team_count && origin_score[score[tmp_id]] == settle) {
if (tmp_id < team_count && !is_winner[score[tmp_id]]) {
winner.push_back(score[tmp_id]);
is_winner[score[tmp_id]] = 1;
// cout << score[tmp_id] << " ?? ";
}
tmp_id ++;
}
}
}
cout << winner.size() << endl;
for (string team : winner) {
cout << team << " ";
}
// cout << "gold: " << settle.first << " " << settle.second << endl;
// string test_team = "K";
// cout << test_team << " : " << best_score[test_team].first << " " << best_score[test_team].second << endl;
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
int T;
cin >>T;
while (T --) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
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: 1ms
memory: 3516kb
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: 1ms
memory: 3824kb
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: 3824kb
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: 376ms
memory: 3652kb
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
Runtime Error
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 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo wJlbqIU 9cy_y_RNRwex8j7224hz 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS _Yej1PrINtydmOudwo...