QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #592046 | #8230. Submissions | AprLsity | WA | 47ms | 3872kb | C++23 | 8.5kb | 2024-09-26 20:16:38 | 2024-09-26 20:16:38 |
Judging History
answer
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<int, int> pii;
typedef array<int, 3> piii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353, P = 131;
struct team
{
ull name;
int pass, tm;
friend bool operator< (team a, team b)
{
if (a.pass == b.pass)
return a.tm < b.tm;
return a.pass > b.pass;
}
};
struct record
{
int tm, id;
char q;
bool ac;
friend bool operator< (record a, record b)
{
if (a.q != b.q)
return a.q < b.q;
if (a.tm != b.tm)
return a.tm < b.tm;
return a.id < b.id;
}
};
int m;
vector<team> t;
vector<ull> ans;
map<ull, vector<record>> rc;
map<ull, string> allteam;
int fstac[26];
bool finish[26];
pii cg[26];
int ac2[26];
int cntac[26];
int lstsub[26];
void init()
{
ans.clear();
t.clear();
rc.clear();
allteam.clear();
for (int i = 0; i < 26; i++)
cntac[i] = ac2[i] = lstsub[i] = 0;
}
void solve()
{
cin >> m;
init();
for (int i = 1; i <= m; i++)
{
string s;
cin >> s;
ull now = 0;
for (int j = 0; j < s.size(); j++)
now = now * P + s[j];
if (rc.count(now) == 0)
allteam[now] = s;
char q;
int tm;
string ac;
cin >> q >> tm >> ac;
rc[now].push_back({tm, i, q, (ac == "accepted")});
}
int et = 0;
for (auto [k, v] : rc)
{
sort(v.begin(), v.end());
char now = v[0].q;
bool ok = false;
int pass = 0, tm = 0;
int nowtm = 0;
for (int i = 0; i < v.size(); i++)
{
if (v[i].q != now)
now = v[i].q, ok = false, nowtm = 0;
if (ok)
continue;
if (v[i].ac)
ok = true, pass++, tm += v[i].tm + nowtm;
else
nowtm += 20;
}
t.push_back({k, pass, tm});
et += pass > 0;
}
sort(t.begin(), t.end());
// if (t[0].pass == 0)
// return;
// cerr << t.size() << endl;
// for (auto it : t)
// cerr << allteam[it.name] << " " << it.pass << " " << it.tm << endl;
int au = min((et + 9) / 10, 35);
int newau = au;
if (t.back().pass == 0)
newau = min(et / 10 + 1, 35);
int lowau = 0, cnt = 0, newlowau = 0;
pii highsc = {0, 0};
for (int i = 0; i < t.size(); i++)
{
if (t[i].pass != highsc.first || t[i].tm != highsc.second)
highsc = {t[i].pass, t[i].tm}, cnt = i;
if (cnt < au)
lowau = i;
if (cnt < newau)
newlowau = i;
if (cnt > au && cnt > newau)
break;
}
// cerr << "lowau: " << lowau << endl;
pii mncg = {inf, -inf};
pii lstmncg = {0, 0};
bool lowauloss = false;
for (int ii = 0; ii < t.size(); ii++)
{
int i = ii;
if (t.back().pass == 0)
{
if (ii == 0)
i = t.size() - 1;
else
i = ii - 1;
}
if (i < lowau)
{
ans.push_back(t[i].name);
continue;
}
for (int j = 0; j < 26; j++)
fstac[j] = finish[j] = 0;
for (auto it : rc[t[i].name])
{
int q = it.q - 'A';
// cerr << i << " " << q << " " << ac2[q] << " " << cntac[q] << endl;
if (finish[q])
continue;
if (i == lowau)
{
if (it.ac && cntac[q])
{
finish[q] = true;
ac2[q] += it.tm;
cntac[q]++;
continue;
}
if (it.ac)
{
fstac[q] += it.tm;
ac2[q] += 20;
cntac[q]++;
continue;
}
if (!cntac[q])
fstac[q] += 20;
ac2[q] += 20;
continue;
}
if (it.ac)
{
fstac[q] += it.tm, finish[q] = true;
continue;
}
fstac[q] += 20;
if (i == t.size() - 1)
lstsub[q] = it.tm;
}
if (i == t.size() - 1)
{
int mx = 0;
for (int j = 0; j < 26; j++)
mx = max(mx, fstac[j] + lstsub[j] - 20);
lstmncg = {1, mx};
}
if (i == lowau)
{
ans.push_back(t[i].name);
if (i + 1 == t.size() || (i > 0 && t[i - 1].pass == t[i].pass && t[i - 1].tm == t[i].tm))
break;
for (int j = 0; j < 26; j++)
{
pii tmp;
if (!cntac[j])
continue;
if (cntac[j] > 1)
tmp = {0, ac2[j] - fstac[j]};
else
tmp = {-1, -fstac[j]};
if (tmp.first < mncg.first)
mncg = tmp;
else if (tmp.first == mncg.first)
mncg.second = max(mncg.second, tmp.second);
}
// cerr << mncg.first << " " << mncg.second << endl;
// cerr << t[i].tm << endl;
if (t[i + 1].pass > t[i].pass + mncg.first || (t[i + 1].pass == t[i].pass + mncg.first && t[i + 1].tm <= t[i].tm + mncg.second))
lowauloss = true;
continue;
}
for (int j = 0; j < 26; j++)
{
if (!finish[j])
fstac[j] = -1;
finish[j] = false;
cg[j] = {0, 0};
}
for (int j = 0; j < 26; j++)
finish[j] = false;
for (int j = 0; j < rc[t[i].name].size(); j++)
{
auto it = rc[t[i].name][j];
int q = it.q - 'A';
// cerr << q << " " << cg[q].first << " " << cg[q].second << endl;
if (finish[q])
continue;
if (it.ac)
{
finish[q] = true;
continue;
}
if (fstac[q] == -1)
cg[q] = {1, it.tm};
else
cg[q] = {0, it.tm - fstac[q]};
// cerr << q << " " << cg[q].first << " " << cg[q].second << endl;
finish[q] = true;
}
pii mxcg = {0, 0};
for (int j = 0; j < 26; j++)
{
if (mxcg.first == cg[j].first)
mxcg.second = min(mxcg.second, cg[j].second);
else if (mxcg.first < cg[j].first)
mxcg = cg[j];
}
bool canau = false;
// cerr << allteam[t[i].name] << " " << mxcg.first << " " << mxcg.second << endl;
if (t[i].pass + mxcg.first > t[lowau].pass || (t[i].pass + mxcg.first == t[lowau].pass && t[i].tm + mxcg.second <= t[lowau].tm))
canau = true;
// cerr << canau << endl;
if ((t[i].pass > t[newlowau].pass || (t[i].pass == t[newlowau].pass && t[i].tm <= t[newlowau].tm)) && (t[i].pass > lstmncg.first || (t[i].pass == lstmncg.first && t[i].tm <= lstmncg.second)))
canau = true;
// cerr << "i: " << i << endl;
// cerr << canau << endl;
if (lowauloss && au == min((et + 8) / 10, 35))
{
if (t[i].pass == t[lowau + 1].pass && t[i].tm == t[lowau + 1].tm)
canau = true;
}
// cerr << canau << endl;
if (t[i].pass == 0)
{
if (t[i].pass + mxcg.first > t[newlowau].pass || (t[i].pass + mxcg.first == t[newlowau].pass && t[i].tm + mxcg.second <= t[newlowau].tm))
canau = true;
}
// if (t[i].pass == t[0].pass && t[i].tm == t[0].tm)
// canau = true;
if (canau)
ans.push_back(t[i].name);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T;
cin >> T;
while (T--)
{
solve();
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
cout << allteam[ans[i]] << " ";
cout << endl;
// cerr << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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 LetItRot ImYourFan AllWayTheNorth XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3556kb
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: 3668kb
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 K A 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: 3872kb
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 K A
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 47ms
memory: 3608kb
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: 35ms
memory: 3648kb
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 Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T tsd 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 pVWDEz 3BQ 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU ...
result:
wrong answer the numbers are different in the case 545. (test case 545)