QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #674171 | #8230. Submissions | ticking_away | WA | 160ms | 3840kb | C++20 | 12.4kb | 2024-10-25 14:21:07 | 2024-10-25 14:21:07 |
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
{
int team;
int time;
bool pass;
char problem;
};
struct team
{
int solve;
int penalty;
// string name;
int team_id;
bool operator<(const team &a) const
{
if (solve == a.solve)
{
if (penalty == a.penalty)
{
return team_id < a.team_id;
}
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;
}
map<string, int> id_mp;
int get_id(string &s)
{
if (id_mp.count(s) == 0)
{
assert(0);
}
return id_mp[s];
}
map<pair<int, char>, vector<sub>> fail_mp; // team prob -> time
map<pair<int, char>, vector<sub>> ac_mp;
map<pair<int, char>, int> penalty_mp;
unordered_map<int, int> team_solve;
unordered_map<int, int> team_penalty;
unordered_set<int> team_list;
map<int, string> name_mp;
void solve()
{
id_mp.clear();
fail_mp.clear();
ac_mp.clear();
penalty_mp.clear();
team_solve.clear();
team_penalty.clear();
team_list.clear();
name_mp.clear();
int m;
cin >> m;
fr(i, 1, m)
{
sub sub;
string suc;
string name;
cin >> name >> sub.problem >> sub.time >> suc;
if (id_mp.count(name) == 0)
{
id_mp[name] = id_mp.size();
sub.team = id_mp[name];
name_mp[id_mp[name]] = name;
}
else
{
sub.team = id_mp[name];
}
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 << name_mp[*team_list.begin()] << endl;
return;
}
vector<team> team_rank;
set<int> final_ans;
for (auto i : team_list)
{
team t;
int id = i;
// t.name = name_mp[id];
t.solve = team_solve[id];
t.team_id = id;
t.penalty = team_penalty[id];
// cout << t.name << " " << t.solve << " " << t.penalty << endl;
team_rank.push_back(move(t));
}
sort(team_rank.begin(), team_rank.end());
// for(auto t:team_rank)
// {
// cout<<t.name<<endl;
// }
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
if (cnt_not_zero == 0)
{
cout << team_list.size() << endl;
auto it = *team_list.begin();
// if (name_mp[it] == "6kW77j5PG66x")
// {
// assert(0);
// }
for (auto id : team_list)
{
cout << name_mp[id] << " ";
}
cout << endl;
return;
}
int mx = min(35, (cnt_not_zero + 9) / 10);
int idx = 0;
int sz = team_rank.size();
vector<int> origin_suc_teams;
for (int i = 0; i < mx; i++)
{
final_ans.insert(team_rank[i].team_id);
origin_suc_teams.push_back(team_rank[i].team_id);
if (idx + 1 < sz)
idx++;
}
if(mx>=sz)
{
cout << final_ans.size() << endl;
for (auto i : final_ans)
{
cout << name_mp[i] << " ";
}
cout << endl;
return;
}
auto last_team = team_rank[mx - 1];
auto nxt_team = team_rank[mx];
while (check_same(team_rank[idx], team_rank[idx - 1]))
{
final_ans.insert(team_rank[idx].team_id);
if (idx + 1 < sz)
idx++;
else
break;
}
bool continue_flag = 0;
for (auto team_name : team_list) // 枚举队伍成绩上升
{
auto name = name_mp[team_name];
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.count({team_name, 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 idx2 = idx;
auto nxt_team = team_rank[idx2];
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.team_id);
if (idx2 + 1 < sz)
{
idx2++;
while (check_same(team_rank[idx2], team_rank[idx2 - 1]))
{
final_ans.insert(team_rank[idx2].team_id);
if (idx2 + 1 < sz)
idx2++;
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)
{
int idx2 = idx;
if (!continue_flag)
{
continue_flag = 1;
final_ans.insert(nxt_team.team_id);
if (idx2 + 1 < sz)
{
idx2++;
while (check_same(team_rank[idx2], team_rank[idx2 - 1]))
{
final_ans.insert(team_rank[idx2].team_id);
if (idx2 + 1 < sz)
idx2++;
else
break;
}
}
}
}
}
}
else
{
// cout<<"!"<<endl;
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)
{
auto Name = name_mp[name];
if (nxt_team_qualify)
break;
for (char problem = 'A'; !nxt_team_qualify && problem <= 'Z'; problem++)
if (ac_mp.count({name, 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.team_id);
if (idx + 1 < sz)
{
idx++;
while (check_same(team_rank[idx], team_rank[idx - 1]))
{
final_ans.insert(team_rank[idx].team_id);
if (idx + 1 < sz)
idx++;
else
break;
}
}
}
cout << final_ans.size() << endl;
for (auto i : final_ans)
{
cout << name_mp[i] << " ";
}
cout << endl;
cerr << m << 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: 3540kb
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: 0ms
memory: 3632kb
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: 0ms
memory: 3572kb
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: 3640kb
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: 49ms
memory: 3840kb
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
Wrong Answer
time: 160ms
memory: 3640kb
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 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 4e1l0pO8eFjZwkDo wJlbqIU 9cy_y_RNRwex8j7224hz 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS _Yej1PrINtydmOudwoO...
result:
wrong answer the numbers are different in the case 7771. (test case 7771)