QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #763782 | #8230. Submissions | RWeakest | WA | 107ms | 3904kb | C++20 | 12.0kb | 2024-11-19 22:04:49 | 2024-11-19 22:04:50 |
Judging History
answer
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <math.h>
#include <cstdio>
#include <vector>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
#define max(x, y) (x > y ? x : y)
#define min(x, y) (x < y ? x : y)
using pii = pair<int, string>;
struct node
{
int tot_problem = 0, tot_time = 0, index = 0;
map<string, bool> flag;
map<string, int> attemp;
priority_queue<int, vector<int>, less<>> minq;
priority_queue<pii, vector<pii>, less<>> maxq;
map<string, int> first_attemp;
priority_queue<pii, vector<pii>, less<>> accept;
map<string, int> time;
map<string, int> second_accept;
};
struct operation
{
string ci, pi, si;
int ti;
};
bool cmp(node a, node b)
{
if (a.tot_problem != b.tot_problem)
return a.tot_problem > b.tot_problem;
else
return a.tot_time < b.tot_time;
}
void solve()
{
int m;
cin >> m;
set<string> ans;
ans.clear();
set<string> team;
team.clear();
map<string, int> index;
map<int, string> team_name;
operation op[m + 1];
for (int i = 1; i <= m; ++i)
{
cin >> op[i].ci >> op[i].pi >> op[i].ti >> op[i].si;
team.emplace(op[i].ci);
if (index.find(op[i].ci) == index.end())
{
int id = team.size();
index[op[i].ci] = id;
team_name[id] = op[i].ci;
}
}
int tot_team = team.size();
node a[tot_team + 1];
for (int i = 1; i <= tot_team; ++i)
{
a[i].attemp.clear();
a[i].flag.clear();
a[i].index = 0;
a[i].tot_problem = 0;
a[i].tot_time = 0;
}
for (int i = 1; i <= m; ++i)
{
int ind = (index.find(op[i].ci)->second);
int oper = (op[i].si == "rejected" ? 0 : 1);
a[ind].index = ind;
// cout << "ind:" << ind << " oper:" << oper << "\n";
// cout << op[i].pi << " " << a[ind].flag.find(op[i].pi)->second << "\n";
if (oper)
{
// cout << op[i].pi << " " << a[ind].flag.find(op[i].pi)->second << "\n";
if (a[ind].flag[op[i].pi])
{
a[ind].time[op[i].pi]++;
a[ind].second_accept[op[i].pi] = min(op[i].ti, a[ind].second_accept[op[i].pi]);
continue;
}
int temp_time = op[i].ti;
if (a[ind].attemp.find(op[i].pi) != a[ind].attemp.end())
temp_time += (a[ind].attemp.find(op[i].pi)->second) * 20;
if (a[ind].first_attemp.find(op[i].pi) != a[ind].first_attemp.end())
a[ind].maxq.emplace(make_pair(temp_time - a[ind].first_attemp.find(op[i].pi)->second, op[i].pi));
a[ind].accept.emplace(make_pair(op[i].ti, op[i].pi));
a[ind].tot_problem++;
a[ind].tot_time = a[ind].tot_time + temp_time;
a[ind].flag[op[i].pi] = true;
a[ind].time[op[i].pi]++;
}
else
{
if (a[ind].flag[op[i].pi])
continue;
a[ind].attemp[op[i].pi]++;
if (a[ind].first_attemp.find(op[i].pi) == a[ind].first_attemp.end())
a[ind].first_attemp[op[i].pi] = op[i].ti;
}
}
for (int i = 1; i <= m; ++i)
{
int ind = (index.find(op[i].ci)->second);
int oper = (op[i].si == "rejected" ? 0 : 1);
if (!oper)
{
if (a[ind].flag[op[i].pi])
continue;
a[ind].minq.emplace(op[i].ti);
}
}
sort(a + 1, a + 1 + tot_team, cmp);
int cnt_team = 0, zero_index = tot_team + 1;
for (int i = 1; i <= tot_team; ++i)
{
if (a[i].tot_problem)
cnt_team++;
else
zero_index = i;
}
int max_gold = min(35, ceil(cnt_team * 0.1));
// for (int i = 1; i <= tot_team; ++i)
// cout << a[i].tot_problem << " " << a[i].tot_time << " " << a[i].index << '\n';
// cout << "max_gold:" << max_gold << "\n";
// 一开始就是金牌
int last_gold_problem = 0, last_gold_time = 0, last_gold_cnt = 1;
for (int i = 1; i <= max_gold; ++i)
{
ans.emplace(team_name.find(a[i].index)->second);
if (i == max_gold)
last_gold_problem = a[i].tot_problem, last_gold_time = a[i].tot_time;
}
// cout << "last_gold_problem:" << last_gold_problem << " last_gold_time:" << last_gold_time << '\n';
for (int i = max_gold + 1; i <= tot_team; ++i)
{
if (a[i].tot_problem == last_gold_problem && a[i].tot_time == last_gold_time)
ans.emplace(team_name.find(a[i].index)->second), last_gold_cnt++;
}
int top_silver_problem = 0, top_silver_time = 0, top_silver_cnt = 0;
top_silver_problem = a[max_gold + 1].tot_problem;
top_silver_time = a[max_gold + 1].tot_time;
for (int i = max_gold + 1; i <= tot_team; ++i)
{
if (a[i].tot_problem == top_silver_problem && a[i].tot_time == top_silver_time)
top_silver_cnt++;
}
// cout << "last_gold_cnt:" << last_gold_cnt << "\n";
// cout << "tot_team:" << tot_team << "\n";
// cout << "cnt_team:" << cnt_team << "\n";
// #1 zero_to_one
if (last_gold_cnt == 1 && zero_index <= tot_team)
{
int temp_max_gold = min(ceil((cnt_team + 1) * 0.1), 35);
// cout << "temp_max_gold:" << temp_max_gold << "\n";
bool flag = false;
// cout << "temp_max_gold:" << temp_max_gold << "\n";
if (temp_max_gold > max_gold)
{
for (int i = zero_index; i <= tot_team; ++i)
{
int temp_tot_time = a[i].tot_time, temp_tot_problem = a[i].tot_problem;
if (!a[i].minq.empty())
{
temp_tot_time += a[i].minq.top();
temp_tot_problem++;
}
else if (!a[i].maxq.empty())
{
temp_tot_time -= a[i].maxq.top().first;
}
// cout << "temp_tot_problem:" << temp_tot_problem << " temp_tot_time:" << temp_tot_time << "\n";
if (temp_tot_problem > top_silver_problem)
{
ans.emplace(team_name.find(a[i].index)->second);
}
else if (temp_tot_problem == top_silver_problem && temp_tot_time < top_silver_time)
{
ans.emplace(team_name.find(a[i].index)->second);
}
else if (temp_tot_problem == top_silver_problem && temp_tot_time == top_silver_time)
{
ans.emplace(team_name.find(a[i].index)->second);
flag = true;
}
}
}
if (flag)
{
for (int i = max_gold + 1; i <= max_gold + top_silver_cnt; ++i)
ans.emplace(team_name.find(a[i].index)->second);
}
if (temp_max_gold == max_gold)
{
// cout << "zero_index:" << zero_index << "\n";
for (int i = zero_index; i <= tot_team; ++i)
{
int temp_tot_time = a[i].tot_time, temp_tot_problem = a[i].tot_problem;
if (!a[i].minq.empty())
{
temp_tot_time += a[i].minq.top();
temp_tot_problem++;
}
else if (!a[i].maxq.empty())
{
temp_tot_time -= a[i].maxq.top().first;
}
// cerr << "temp_tot_problem:" << temp_tot_problem << " temp_tot_time:" << temp_tot_time << "\n";
if (temp_tot_problem > last_gold_problem)
ans.emplace(team_name.find(a[i].index)->second);
else if (temp_tot_problem == last_gold_problem && temp_tot_time >= last_gold_time)
ans.emplace(team_name.find(a[i].index)->second);
}
}
}
// #2 silver_to_gold
for (int i = max_gold + last_gold_cnt; i < zero_index; ++i)
{
// cout << "i:" << i << "\n";
int temp_tot_time = a[i].tot_time, temp_tot_problem = a[i].tot_problem;
if (!a[i].minq.empty())
{
temp_tot_time += a[i].minq.top();
temp_tot_problem++;
}
else if (!a[i].maxq.empty())
{
temp_tot_time -= a[i].maxq.top().first;
}
// cout << "temp_tot_problem:" << temp_tot_problem << " temp_tot_time:" << temp_tot_time << "\n";
if (temp_tot_problem > last_gold_problem)
{
// cout << 1 << "\n";
ans.emplace(team_name.find(a[i].index)->second);
}
else if (temp_tot_problem == last_gold_problem && temp_tot_time <= last_gold_time)
{
// cout << 2 << "\n";
ans.emplace(team_name.find(a[i].index)->second);
}
}
// #3 gold_to_silver
// cout << "cnt_team:" << cnt_team << "\n";
if (last_gold_cnt == 1)
{
int temp_max_gold = max_gold;
if (last_gold_problem == 1)
temp_max_gold = min(35, ceil((cnt_team - 1) * 0.1));
// cout << "max_gold:" << max_gold << " temp_max_gold:" << temp_max_gold << "\n";
bool flag1 = false, flag2 = false, flag3 = false;
if (temp_max_gold == max_gold)
flag1 = true;
if (a[1].tot_problem > 1)
flag3 = true;
// cout << "temp_max_gold:" << temp_max_gold << "\n";
// cout << "flag1:" << flag1 << " flag3:" << flag3 << "\n";
if (flag1 || flag3)
{
for (int i = 1; i <= max_gold; ++i)
{
if (!flag1 && a[i].tot_problem == 1)
continue;
int temp_tot_time = a[i].tot_time, temp_tot_problem = a[i].tot_problem;
// cout << "temp_tot_problem:" << temp_tot_problem << " temp_tot_time:" << temp_tot_time << "\n";
int first_accept = 300, second_accept = 0, temp_second_accept = 0;
while (!a[i].accept.empty())
{
auto x = a[i].accept.top();
a[i].accept.pop();
if ((a[i].time.find(x.second)->second) == 1)
first_accept = min(first_accept, x.first);
else
{
if (a[i].second_accept.find(x.second)->second > second_accept)
{
second_accept = a[i].second_accept.find(x.second)->second;
temp_second_accept = x.first;
}
}
}
// cout << "first_accept:" << first_accept << "\n";
if (first_accept != 300)
{
temp_tot_problem--;
temp_tot_time -= first_accept;
}
else
{
temp_tot_time -= temp_second_accept;
temp_tot_time += second_accept + 20;
}
// cout << "temp_tot_problem:" << temp_tot_problem << " temp_tot_time:" << temp_tot_time << "\n";
if (temp_tot_problem < top_silver_problem)
flag2 = true;
else if (temp_tot_problem == top_silver_problem && temp_tot_time > top_silver_time)
flag2 = true;
}
if (flag2)
{
for (int i = max_gold + 1; i <= max_gold + top_silver_cnt; ++i)
ans.emplace(team_name.find(a[i].index)->second);
}
}
}
cout << ans.size() << "\n";
for (auto x : ans)
cout << x << " ";
cout << "\n";
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3672kb
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: 3856kb
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: 3904kb
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: 3676kb
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: 63ms
memory: 3640kb
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: 107ms
memory: 3656kb
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 4 ADrO7CHWWKZ_Kefn PezeyUurYoz7N1i...
result:
wrong answer the numbers are different in the case 12. (test case 12)