QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #738358 | #8230. Submissions | The_cosmos | WA | 76ms | 15048kb | C++14 | 6.4kb | 2024-11-12 18:49:02 | 2024-11-12 18:49:29 |
Judging History
answer
// A
#include <bits/stdc++.h>
using namespace std;
using db = double;
using lb = long double;
using ull = unsigned long long;
using uint = unsigned int;
using ll = long long;
//using i128 = __int128;
//using ui128 = unsigned __int128;
#define REP(i, first, last) for(int i = (first); i <= (last); ++ i)
#define DOW(i, first, last) for(int i = (first); i >= (last); -- i)
#define int long long
#define pb emplace_back
#define ob pop_back
#define pii pair<int, int>
#define MPR make_pair
#define fi first
#define se second
#define tpl tuple<int, int, int>
#define MTP make_tuple
#define poly vector<int>
#define polyp vector<pii>
#define polyt vector<tpl>
#define all(x) x.begin(), x.end()
#define CVR(a, q) memset(a, q, sizeof a)
#define CLR(a) memset(a, 0, sizeof a)
#define CPY(a, q) memcpy(a, q, sizeof a)
#define PCT __builtin_popcount
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod1 = 1e9 + 7, mod2 = 998244353, mod = 1e9 + 7;
const long long inf = 1e18;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<string, int> mp;
unordered_map<int, string> pre;
// opt 表示当前题目哪些队过了
int idx = 0;
int id(string s) {
if(!mp.count(s)) return pre[idx + 1] = s, mp[s] = ++ idx;
return mp[s];
}
int cnt[N][30];// cnt 表示当前题目有多少个人通过了
pair<pii, string> po[N];// po 表示第 i 个队伍的 {过题数，时间}
// bool check(pair<pii, string> x, pair<pii, string> y) {
// return x.fi.fi > y.fi.fi || x.fi.se < y.fi.se;
// }
bool cmp(pair<pii, string> x, pair<pii, string> y) {
if(x.fi.fi != y.fi.fi) return x.fi.fi > y.fi.fi;
return x.fi.se < y.fi.se;
}
void Solve() {
int m; cin >> m;
mp.clear(), idx = 0;
REP(i, 1, 26) REP(j, 1, m) cnt[j][i] = 0;
poly acc[m + 1][30], rej[m + 1][30];
REP(i, 1, m) {
char p;
int t;
string c, s;
cin >> c >> p >> t >> s;
// cerr << t << '\n';
int x = id(c);
int nt = t + cnt[x][p - 64] * 20;
if(s[0] == 'a') acc[x][p - 64].pb(nt);
else rej[x][p - 64].pb(nt);
cnt[x][p - 64] ++;
}
int n = idx;
// cerr << "qwq";
//团队个数
REP(i, 1, n) {
int w = 0, sum = 0;
REP(j, 1, 26) if(acc[i][j].size()) w ++, sum += acc[i][j][0];
po[i] = {{w, sum}, pre[i]};
// cerr << pre[i] << ' ' << w << '\n';
}
sort(po + 1, po + n + 1, cmp);
int dddn = n;
// cerr << n << '\n';
REP(i, 1, n) {
int x = id(po[i].se);
REP(j, 1, 26) if(acc[x][j].size()) goto p1;
n = i - 1; break;
p1 : continue;
}
// cerr << n << '\n';
unordered_map<string, bool> se;
int Auline = min((int)ceil(0.1 * n), 35ll);
REP(i, 1, n) {
// cerr << po[i].se << ' ' << po[i].fi.fi << ' ' << po[i].fi.se << '\n';
if(po[i].fi.fi > po[Auline].fi.fi) se[po[i].se] = 1;
else if(po[i].fi.fi == po[Auline].fi.fi && po[i].fi.se <= po[Auline].fi.se)
se[po[i].se] = 1;
}
// cerr << n << '\n';
//1.本来就可以拿 Au 的。
// cout << se.size() << '\n';
// for(auto it : se) cout << (it.first) << ' ';
// cout << '\n';
REP(i, 1, n) {
if(po[i].fi.fi != po[Auline].fi.fi - 1) continue;
int ti = po[i].fi.se, x = id(po[i].se);
REP(j, 1, 26) {
if(!rej[x][j].size() || acc[x][j].size()) continue;
if(ti + rej[x][j][0] <= po[Auline].fi.se) se[po[i].se] = 1;
}
}
// cout << se.size() << '\n';
// for(auto it : se) cout << (it.first) << ' ';
// cout << '\n';
//2. 自己改掉可以拿 Au 的。
// cerr << po[3].se << '\n' << po[3].fi.se << ' ' << po[3].fi.fi << '\n';
if(Auline < n) {
// cerr << po[Auline].se << '\n' << po[Auline + 1].se << ' ' << po[Auline + 1].fi.se << '\n';
REP(i, 1, Auline) {
int w = po[i].fi.fi, sum = po[i].fi.se;
int x = id(po[i].se);
REP(j, 1, 26) {
if(!acc[x][j].size()) continue;
if(acc[x][j].size() == 1) {
int nw = w - 1, ns = sum - acc[x][j][0];
if(!nw) {
int ppip = Auline;
ppip = min((int)ceil(0.1 * (n - 1)), 35ll);
// cerr << ppip << ' ' << Auline << '\n';
if(ppip == Auline) {
se[po[Auline + 1].se] = 1;
break;
}
}
else if(!cmp({{nw, ns}, ""}, po[Auline + 1])) {
se[po[Auline + 1].se] = 1;
// cerr << nw << ' ' << ns << '\n';
break;
}
}
else {
int nw = w, ns = sum - acc[x][j][0] + acc[x][j][1];
if(!cmp({{nw, ns}, ""}, po[Auline + 1])) {
se[po[Auline + 1].se] = 1;
break;
}
}
}
if(se.count(po[Auline + 1].se)) break;
}
if(se.count(po[Auline + 1].se))
REP(i, Auline + 2, n) {
if(po[i].fi.fi == po[Auline + 1].fi.fi && po[i].fi.se == po[Auline + 1].fi.se)
se[po[i].se] = 1;
}
}
// cout << se.size() << '\n';
// for(auto it : se) cout << (it.first) << ' ';
// cout << '\n';
//3.别人退下来。
// cerr << n << '\n';
if(n < dddn) {
pair<pii, string> maxn = {{1, inf}, ""};
Auline = min((int)ceil(0.1 * (n + 1)), 35ll);
if(po[Auline].fi.fi == 1)
REP(t, n + 1, dddn) {
int x = id(po[t].se);
int minn = inf;
REP(i, 1, 26)
if(rej[x][i].size()) {
minn = min(minn, rej[x][i][0]);
}
REP(i, 1, 26)
if(rej[x][i].size() && minn == rej[x][i][0]) {
if(minn <= po[Auline].fi.fi) {
se[po[t].se] = 1;
break;
}
}
// acc[x][i].pb(minn);
}
REP(t, n + 1, dddn) {
int x = id(po[t].se);
REP(i, 1, 26)
if(rej[x][i].size()) {
if(maxn.fi.se == inf || !cmp({{1, rej[x][i].back()}, po[t].se}, maxn))
maxn = {{1, rej[x][i].back()}, po[t].se};
}
}
n ++, po[n] = maxn;
// cerr << maxn.se << ' ' << maxn.fi.fi << ' ' << maxn.fi.se << '\n';
sort(po + 1, po + n + 1, cmp);
// cerr << po[Auline].se << ' ' << po[Auline].fi.fi << ' ' << po[Auline].fi.se << '\n';
// cerr << Auline << '\n';
// cerr << n << '\n';
REP(i, 1, n) {
// cerr << po[i].se << ' ' << po[i].fi.fi << ' ' << po[i].fi.se << '\n';
if(po[i].fi.fi > po[Auline].fi.fi) se[po[i].se] = 1;
else if(po[i].fi.fi == po[Auline].fi.fi && po[i].fi.se <= po[Auline].fi.se)
se[po[i].se] = 1;
}
}
cout << se.size() << '\n';
for(auto it : se) cout << (it.first) << ' ';
cout << '\n';
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
cin >> T;
while (T --) {
Solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13300kb
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 ImYourFan LetItRot XuejunXinyoudui1 AllWayTheNorth
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 15048kb
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: 14028kb
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 J G F H B E K I D C A 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 2ms
memory: 14268kb
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 B A 2 K A
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 76ms
memory: 14700kb
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: 64ms
memory: 13412kb
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 xiLm0TUOF3T tsd fYuK1KNkuyO5HRCq Qua1Pti3vKhyQKDUm 2 JP t3 2 77sgqpbTIr_Zt1 fhYPGC8W82NwJTQL 1 3BQ 1 buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 ALTqPt7JUSLrl vwfw 1 QTEzV6tp 3 wJlbqIU 4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz 2 6mbCu5zA eiuF7a_ 1 xy6QBr8ECi 2 PezeyUurYoz7N1iGU ldaKLZb1oS1sS 4 idqV8Np...
result:
wrong answer the numbers are different in the case 4. (test case 4)