QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #673492 | #8230. Submissions | ticking_away | RE | 55ms | 3808kb | C++20 | 10.8kb | 2024-10-24 22:57:04 | 2024-10-24 22:57:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)
/**
____ ___ _____
/ ___| _ _ / _ \___ /
\___ \| | | | | | ||_ \
___) | |_| | |_| |__) |
|____/ \__, |\___/____/
|___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
for (auto &i : v)
in >> i;
return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
for (auto &i : v)
out << i << " ";
return out;
}
bool _output = 1;
struct sub
{
string team;
int time;
bool pass;
char problem;
};
struct team
{
int solve;
int penalty;
string name;
bool operator<(const team &a) const
{
if (solve == a.solve)
{
if (penalty == a.penalty)
{
return name < a.name;
}
return penalty < a.penalty;
}
return solve > a.solve;
}
};
bool check_same(team a, team b)
{
if (a.solve != b.solve)
return 0;
if (a.penalty != b.penalty)
return 0;
return 1;
}
void solve()
{
map<pair<string, char>, vector<sub>> fail_mp; // team prob -> time
map<pair<string, char>, vector<sub>> ac_mp;
map<pair<string, char>, int> penalty_mp;
unordered_map<string, int> team_solve;
unordered_map<string, int> team_penalty;
unordered_set<string> team_list;
vector<sub> all_sub_list;
int m;
cin >> m;
fr(i, 1, m)
{
sub sub;
string suc;
cin >> sub.team >> sub.problem >> sub.time >> suc;
if (suc == "accepted")
{
sub.pass = 1;
if (ac_mp[{sub.team, sub.problem}].size() == 0)
{
int penalty = sub.time + 20 * (fail_mp[{sub.team, sub.problem}].size());
team_penalty[sub.team] += penalty;
penalty_mp[{sub.team, sub.problem}] = penalty;
team_solve[sub.team]++;
}
ac_mp[{sub.team, sub.problem}].push_back(sub);
}
else
{
sub.pass = 0;
fail_mp[{sub.team, sub.problem}].push_back(sub);
}
team_list.insert(sub.team);
}
if (m == 1)
{
cout << 1 << endl;
cout << *team_list.begin() << endl;
return;
}
vector<team> team_rank;
set<string> final_ans;
for (auto i : team_list)
{
team t;
t.name = i;
t.solve = team_solve[i];
t.penalty = team_penalty[i];
// cout << t.name << " " << t.solve << " " << t.penalty << endl;
team_rank.push_back(t);
}
sort(team_rank.begin(), team_rank.end());
int cnt_not_zero = 0;
for (auto name : team_list)
{
if (team_solve[name] != 0)
{
cnt_not_zero++;
}
}
bool sp1 = (cnt_not_zero) % 10 == 1; // TODO
bool sp0 = (cnt_not_zero) % 10 == 0; // TODO
int mx = min(35, (cnt_not_zero + 9) / 10);
auto it = team_rank.begin();
vector<string> origin_suc_teams;
for (int i = 0; i < mx; i++)
{
final_ans.insert(it->name);
origin_suc_teams.push_back(it->name);
if (it != prev(team_rank.end()))
it++;
}
auto last_team = *prev(it);
auto nxt_team = *it;
while (check_same(*it, *prev(it)))
{
final_ans.insert(it->name);
if (it != prev(team_rank.end()))
it++;
}
bool continue_flag = 0;
// 枚举队伍成绩上升
for (auto team_name : team_list) //
{
auto last_solve = last_team.solve;
auto last_penalty = last_team.penalty;
// cout << team_name << endl;
if (final_ans.count(team_name))
continue;
bool suc = 0;
for (char problem = 'A'; problem <= 'Z'; problem++)
if (fail_mp[{team_name, problem}].size() > 0) // 有未通过的题目
{
auto sub = *fail_mp[{team_name, problem}].begin();
int now_solve = team_solve[team_name];
int now_penalty = team_penalty[team_name];
if (ac_mp[{team_name, problem}].size() == 0)
{
now_solve++;
now_penalty += sub.time;
if (now_solve == 1 && sp0)
{
auto it2 = it;
auto nxt_team = *it2;
if (nxt_team.solve < now_solve)
{
suc = 1;
final_ans.insert(team_name);
}
if (nxt_team.solve == now_solve && nxt_team.penalty >= now_penalty)
{
suc = 1;
final_ans.insert(team_name);
}
if (nxt_team.solve > now_solve || nxt_team.solve == now_solve && nxt_team.penalty <= now_penalty)
{
final_ans.insert(nxt_team.name);
if (!continue_flag)
{
continue_flag = 1;
if ((it2) != prev(team_rank.end()))
{
it2++;
while (check_same(*it2, *prev(it2)))
{
final_ans.insert(it2->name);
if (it2 != prev(team_rank.end()))
it2++;
else
break;
}
}
}
}
// last sub
now_penalty = team_penalty[team_name];
sub = *fail_mp[{team_name, problem}].rbegin();
now_penalty += fail_mp[{team_name, problem}].size() * 20 - 20 + sub.time;
// if (team_name == "K" && problem == 'K')
// {
// cout << now_penalty << " " << now_solve << endl;
// }
if (nxt_team.solve == now_solve && nxt_team.penalty >= now_penalty)
{
suc = 1;
final_ans.insert(team_name);
}
if (nxt_team.solve > now_solve || nxt_team.solve == now_solve && nxt_team.penalty <= now_penalty)
{
auto it2 = it;
if (!continue_flag)
{
continue_flag = 1;
final_ans.insert(nxt_team.name);
if ((it2) != prev(team_rank.end()))
{
it2++;
while (check_same(*it2, *prev(it2)))
{
final_ans.insert(it2->name);
if (it2 != prev(team_rank.end()))
it2++;
else
break;
}
}
}
}
}
}
else
{
auto ac_time = *ac_mp[{team_name, problem}].begin();
if (sub.time < penalty_mp[{team_name, problem}])
{
now_penalty += sub.time - penalty_mp[{team_name, problem}];
}
}
if (last_solve < now_solve || (last_solve == now_solve && last_penalty >= now_penalty))
{
suc = 1;
final_ans.insert(team_name);
}
}
}
// 枚举队伍成绩下降
bool nxt_team_qualify = 0;
int nxt_team_solve = nxt_team.solve;
int nxt_team_penalty = nxt_team.penalty;
for (auto name : origin_suc_teams)
{
if (nxt_team_qualify)
break;
for (char problem = 'A'; !nxt_team_qualify && problem <= 'Z'; problem++)
{
if (ac_mp[{name, problem}].size() == 0)
{
continue;
}
auto sub = *ac_mp[{name, problem}].begin();
int now_solve = team_solve[name];
int now_penalty = team_penalty[name] - penalty_mp[{name, problem}];
if (ac_mp[{name, problem}].size() == 1) // 只有一次成功提交
{
now_solve--;
if (nxt_team_solve > now_solve || (nxt_team_solve == now_solve && nxt_team_penalty <= now_penalty))
{
if (!(now_solve == 0 && sp1))
nxt_team_qualify = 1;
}
}
else // 多次成功提交，找到第二次提交
{
auto it = ac_mp[{name, problem}].begin();
it++;
now_penalty += it->time + 20;
if (nxt_team_solve > now_solve || (nxt_team_solve == now_solve && nxt_team_penalty <= now_penalty))
{
if (!(now_solve == 0 && sp1))
nxt_team_qualify = 1;
}
}
}
}
if (nxt_team_qualify)
{
final_ans.insert(nxt_team.name);
if ((it) != prev(team_rank.end()))
{
it++;
while (check_same(*it, *prev(it)))
{
final_ans.insert(it->name);
if (it != prev(team_rank.end()))
it++;
else
break;
}
}
}
cout << final_ans.size() << endl;
for (auto i : final_ans)
{
cout << i << " ";
}
cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1;
if (_output)
cin >> _;
while (_--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 3680kb
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: 1ms
memory: 3604kb
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: 1ms
memory: 3808kb
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: 55ms
memory: 3536kb
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 4Vf5RXaTmySkFcXgHLOh 1...
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...