QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #324359 | #8230. Submissions | ucup-team045# | WA | 0ms | 3780kb | C++20 | 10.6kb | 2024-02-10 17:59:45 | 2024-02-10 17:59:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int m;
cin >> m;
map<string, int> mp;
vector<string> name;
vector<vector<array<int, 3> > > sub;
vector<array<int, 26> > pe;
int idx = 0;
auto get = [&](const string &s){
if (!mp.contains(s)){
mp[s] = idx++;
name.push_back(s);
sub.push_back({});
pe.push_back({});
}
return mp[s];
};
while(m--){
string s; char a; int b; string state;
cin >> s >> a >> b >> state;
int id = get(s);
sub[id].push_back({a - 'A', b, state[0] == 'a'});
}
vector<pair<int, int> > p(idx);
int vaild = 0;
for(int i = 0; i < idx; i++){
int pre[26]{};
for(auto [a, b, c] : sub[i]){
if (pre[a] == -1) continue;
if (c == 1){
p[i].first -= 1;
pe[i][a] = b + 20 * pre[a];
p[i].second += b + 20 * pre[a];
pre[a] = -1;
}
else{
pre[a] += 1;
}
}
if (p[i].first != 0){
vaild += 1;
}
}
auto q = p;
sort(q.begin(), q.end());
vector<int> ans;
// 合法人数不变
{
const int target = min((vaild + 9) / 10, 35);
vector<int> cand;
pair<int, int> t;
for(int i = 0; i < idx; i++){
int c = lower_bound(q.begin(), q.end(), p[i]) - q.begin();
if (c == target){
cand.push_back(i);
t = p[i];
}
}
bool ok = false;
for(int i = 0; i < idx; i++){
if (p[i].first == 0) continue;
pair<int, int> best = p[i];
vector<int> v[26][2];
vector<pair<int, int> > v2[26];
for(auto [a, b, c] : sub[i]){
v[a][c].push_back(b);
v2[a].push_back({b, c});
}
for(int j = 0; j < 26; j++){
if (v[j][1].empty()){
if (!v[j][0].empty()){
auto cur = p[i];
cur.first -= 1;
cur.second -= pe[i][j];
cur.second += v[j][0][0];
best = min(best, cur);
}
}
else{
int mn = 1e9;
if (!v[j][0].empty()){
mn = min(mn, v[j][0][0]);
}
if (!v[j][1].empty()){
mn = min(mn, v[j][1][0]);
}
auto cur = p[i];
cur.second -= pe[i][j];
cur.second += mn;
best = min(best, cur);
}
}
int tot = lower_bound(q.begin(), q.end(), best) - q.begin();
if (tot < target){
ans.push_back(i);
}
if (p[i] < t && t.first != 0){
auto bad = p[i];
for(int j = 0; j < 26; j++){
if (v[j][1].empty()) continue;
if (v[j][1].size() == 1){
auto cur = p[i];
cur.first += 1;
cur.second -= pe[i][j];
bad = max(bad, cur);
}
else{
auto cur = p[i];
cur.second -= pe[i][j];
bool flag = false;
for(auto [b, c] : v2[j]){
if (c == 0) cur.second += 20;
else if (!flag){
flag = true;
cur.second += 20;
}
else{
cur.second += b;
break;
}
}
if (cur.first != 0) bad = max(bad, cur);
}
}
if (t <= bad){
ok = true;
}
}
}
if (ok && t.first != 0){
for(auto x : cand){
ans.push_back(x);
}
}
}
// 总人数加一.
if (vaild < idx){
const int target = min((vaild + 1 + 9) / 10, 35);
for(int i = 0; i < idx; i++){
if (p[i].first != 0) continue;
pair<int, int> best = p[i];
vector<int> v[26][2];
vector<pair<int, int> > v2[26];
for(auto [a, b, c] : sub[i]){
v[a][c].push_back(b);
v2[a].push_back({b, c});
}
for(int j = 0; j < 26; j++){
if (v[j][1].empty()){
if (!v[j][0].empty()){
auto cur = p[i];
cur.first -= 1;
cur.second -= pe[i][j];
cur.second += v[j][0][0];
best = min(best, cur);
}
}
else{
int mn = 1e9;
if (!v[j][0].empty()){
mn = min(mn, v[j][0][0]);
}
if (!v[j][1].empty()){
mn = min(mn, v[j][1][0]);
}
auto cur = p[i];
cur.second -= pe[i][j];
cur.second += mn;
best = min(best, cur);
}
}
if (best.first != 0){
int tot = lower_bound(q.begin(), q.end(), best) - q.begin();
if (tot < target){
ans.push_back(i);
}
}
}
}
// 总人数减一
if (vaild > 0){
const int target = min((vaild - 1 + 9) / 10, 35);
vector<int> cand;
pair<int, int> t;
for(int i = 0; i < idx; i++){
int c = lower_bound(q.begin(), q.end(), p[i]) - q.begin();
if (c == target){
cand.push_back(i);
t = p[i];
}
}
bool ok = false;
for(int i = 0; i < idx; i++){
if (p[i].first != 1) continue;
vector<int> v[26][2];
vector<pair<int, int> > v2[26];
for(auto [a, b, c] : sub[i]){
v[a][c].push_back(b);
v2[a].push_back({b, c});
}
if (p[i] < t){
auto bad = p[i];
for(int j = 0; j < 26; j++){
if (v[j][1].empty()) continue;
if (v[j][1].size() == 1){
auto cur = p[i];
cur.first += 1;
cur.second -= pe[i][j];
bad = max(bad, cur);
}
else{
auto cur = p[i];
cur.second -= pe[i][j];
bool flag = false;
for(auto [b, c] : v2[j]){
if (c == 0) cur.second += 20;
else if (!flag){
flag = true;
cur.second += 20;
}
else{
cur.second += b;
break;
}
}
if (cur.first != 0) bad = max(bad, cur);
}
}
if (t <= bad){
ok = true;
}
}
}
if (ok && t.first != 0){
for(auto x : cand){
ans.push_back(x);
}
}
}
// 总人数加一 2
{
const int target1 = min((vaild + 9) / 10, 35);
const int target = min((vaild + 1 + 9) / 10, 35);
int mx = -1;
if (target > target1){
for(int i = 0; i < idx; i++){
if (p[i].first != 0) continue;
pair<int, int> best = p[i];
vector<pair<int, int> > v2[26];
for(auto [a, b, c] : sub[i]){
v2[a].push_back({b, c});
}
for(int j = 0; j < 26; j++){
if (!v2[j].empty()){
mx = max(mx, int(v2[j].size() - 1) * 20 + v2[j].back().first);
}
}
}
}
if (mx != -1){
q.push_back({-1, mx});
sort(q.begin(), q.end());
for(int i = 0; i < idx; i++){
int tot = lower_bound(q.begin(), q.end(), p[i]) - q.begin();
if (tot < target){
ans.push_back(i);
}
}
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << '\n';
for(auto x : ans) cout << name[x] << ' ';
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
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: 3780kb
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: 3608kb
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: -100
Wrong Answer
time: 0ms
memory: 3612kb
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:
11 A B C D E F G H I J K 2 A K
result:
wrong answer the numbers are different in the case 1. (test case 1)