QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #325079 | #8230. Submissions | ucup-team180# | WA | 0ms | 3844kb | C++17 | 5.5kb | 2024-02-11 03:59:45 | 2024-02-11 03:59:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for (int i = 0; i < t; i++){
int m;
cin >> m;
vector<string> c(m);
vector<char> p(m);
vector<int> t(m);
vector<string> s(m);
for (int j = 0; j < m; j++){
cin >> c[j] >> p[j] >> t[j] >> s[j];
}
vector<string> team = c;
sort(team.begin(), team.end());
team.erase(unique(team.begin(), team.end()), team.end());
int cnt = team.size();
vector<int> idx(m);
for (int j = 0; j < m; j++){
idx[j] = lower_bound(team.begin(), team.end(), c[j]) - team.begin();
}
vector<vector<int>> sub_idx(cnt);
for (int j = 0; j < m; j++){
sub_idx[idx[j]].push_back(j);
}
vector<int> prb_idx(m);
vector<vector<char>> prb(cnt);
vector<int> prb_cnt(cnt);
vector<vector<vector<int>>> sub(cnt);
for (int j = 0; j < cnt; j++){
for (int k : sub_idx[j]){
prb[j].push_back(p[k]);
}
sort(prb[j].begin(), prb[j].end());
prb[j].erase(unique(prb[j].begin(), prb[j].end()), prb[j].end());
for (int k : sub_idx[j]){
prb_idx[k] = lower_bound(prb[j].begin(), prb[j].end(), p[k]) - prb[j].begin();
}
prb_cnt[j] = prb[j].size();
sub[j].resize(prb_cnt[j]);
for (int k : sub_idx[j]){
sub[j][prb_idx[k]].push_back(k);
}
}
vector<pair<int, int>> score(cnt);
for (int j = 0; j < cnt; j++){
int ac = 0, time = 0;
for (int k = 0; k < prb_cnt[j]; k++){
int time_add = 0;
for (int l : sub[j][k]){
if (s[l] == "accepted"){
ac++;
time += t[l];
break;
}
if (s[l] == "rejected"){
time_add += 20;
}
}
}
score[j] = make_pair(ac, time);
}
auto score_comp = [&](pair<int, int> P1, pair<int, int> P2){
return P1.first > P2.first || P1.first == P2.first && P1.second < P2.second;
};
vector<int> rank(cnt);
for (int j = 0; j < cnt; j++){
rank[j] = j;
}
sort(rank.begin(), rank.end(), [&](int x, int y){
return score_comp(score[x], score[y]);
});
vector<int> rank_inv(cnt);
for (int j = 0; j < cnt; j++){
rank_inv[rank[j]] = j;
}
vector<pair<int, int>> score_sort(cnt);
for (int j = 0; j < cnt; j++){
score_sort[j] = score[rank[j]];
}
int n = lower_bound(score_sort.begin(), score_sort.end(), make_pair(0, 0), score_comp) - score_sort.begin();
vector<int> imos(cnt + 1, 0);
if (n > 0){
imos[0]++;
imos[upper_bound(score_sort.begin(), score_sort.end(), score_sort[min((n + 9) / 10, 35) - 1], score_comp) - score_sort.begin()]--;
}
for (int j = 0; j < cnt; j++){
for (int k = 0; k < prb_cnt[j]; k++){
int sub_cnt = sub[j][k].size();
vector<int> ac;
for (int l = 0; l < sub_cnt; l++){
if (s[sub[j][k][l]] == "accepted"){
ac.push_back(l);
}
}
vector<int> sum(sub_cnt + 1);
sum[0] = 0;
for (int l = 0; l < sub_cnt; l++){
sum[l + 1] = sum[l];
if (s[sub[j][k][l]] == "rejected"){
sum[l + 1] += 20;
}
}
for (int l = 0; l < sub_cnt; l++){
if (s[sub[j][k][l]] == "accepted"){
pair<int, int> new_score = score[j];
if (ac.size() == 1){
new_score.first--;
new_score.second -= sum[l] + t[sub[j][k][l]];
} else if (l == ac[0]){
new_score.second += sum[ac[1]] - sum[ac[0]] + t[sub[j][k][ac[1]]] - t[sub[j][k][ac[0]]];
}
int new_n = n;
if (new_score.first == 0){
new_n--;
}
if (new_n > 0){
imos[0]++;
int p = min((new_n + 9) / 10, 35);
if (!score_comp(score_sort[p - 1], score[j]) && !score_comp(new_score, score_sort[p])){
p++;
}
imos[upper_bound(score_sort.begin(), score_sort.end(), score_sort[p - 1], score_comp) - score_sort.begin()]--;
}
}
if (s[sub[j][k][l]] == "rejected"){
pair<int, int> new_score = score[j];
if (ac.size() == 0){
new_score.first++;
new_score.second += sum[l] + t[sub[j][k][l]];
} else if (l < ac[0]){
new_score.second += sum[l] + t[sub[j][k][l]] - sum[ac[0]] - t[sub[j][k][ac[0]]];
}
int new_n = n;
if (score[j].first == 0 && new_score.second == 1){
new_n++;
}
if (new_n > 0){
int cnt_higher = lower_bound(score_sort.begin(), score_sort.end(), new_score, score_comp) - score_sort.begin();
if (cnt_higher < min((new_n + 9) / 10, 35)){
imos[rank_inv[j]]++;
imos[rank_inv[j] + 1]--;
}
}
}
}
}
}
for (int j = 0; j < cnt; j++){
imos[j + 1] += imos[j];
}
vector<string> ans;
for (int j = 0; j < cnt; j++){
if (imos[j] > 0){
ans.push_back(team[rank[j]]);
}
}
int k = ans.size();
cout << k << '\n';
for (int j = 0; j < k; j++){
cout << ans[j];
if (j < k - 1){
cout << ' ';
}
}
cout << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
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 XuejunXinyoudui1 AllWayTheNorth ImYourFan LetItRot
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
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: -100
Wrong Answer
time: 0ms
memory: 3564kb
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:
2 A K 1 A
result:
wrong answer the numbers are different in the case 1. (test case 1)