QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #547387 | #8230. Submissions | ucup-team4821 | WA | 75ms | 72680kb | C++14 | 6.6kb | 2024-09-04 21:12:02 | 2024-09-04 21:12:02 |
Judging History
answer
#include <bits/stdc++.h>
int T, n, m, a[100005], b[100005], c[100005], rk[100005], addtim;
std::pair<int, int> best[100005], now[100005], worst[100005];
std::string f[100005];
std::pair<int, int> max[100005];
bool pp[100005];
bool d[100005];
std::vector<int> e[100005][26], ans;
std::map<std::string, int> map;
bool cmp(const std::pair<int, int> &A, const std::pair<int, int> &B) { return A.first == B.first ? A.second < B.second : A.first > B.first; }
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> T;
while (T--)
{
std::cin >> n;
m = 0;
addtim = -1;
for (int i = 1; i <= n; ++i)
{
static std::string str1, str2;
static char c1;
std::cin >> str1 >> c1 >> c[i] >> str2;
a[i] = map.insert({str1, map.size()}).first->second;
b[i] = c1 - 'A';
d[i] = str2 == "accepted";
e[a[i]][b[i]].push_back(i);
}
for (auto i : map)
f[i.second] = i.first;
for (std::size_t i = 0; i != map.size(); ++i)
{
for (int j = 0; j != 26; ++j)
{
int cur = 0;
for (auto k : e[i][j])
if (d[k])
{
now[i].first += 1;
now[i].second += cur * 20 + c[k];
break;
}
else
++cur;
}
}
std::iota(rk, rk + map.size(), 0);
std::sort(rk, rk + map.size(), [&](const int &A, const int &B)
{ return cmp(now[A], now[B]); });
for (std::size_t i = 0; i != map.size(); ++i)
{
if (now[i].first == 0)
for (int j = 0; j != 26; ++j)
if (!e[i][j].empty())
addtim = std::max(addtim, c[e[i][j].back()] + int(e[i][j].size() - 1) * 20);
m += bool(now[i].first);
best[i] = worst[i] = now[i];
for (int j = 0; j != 26; ++j)
{
static std::vector<int>::iterator p;
int cur = 0;
bool found = false;
for (auto k : e[i][j])
if (d[k])
{
cur = cur * 20 + c[k];
found = true;
break;
}
else
++cur;
p = std::find_if(e[i][j].begin(), e[i][j].end(), [&](const int &X)
{ return !d[X]; });
if (p != e[i][j].end())
{
d[*p] ^= true;
int curr = 0;
bool foundr = false;
for (auto k : e[i][j])
if (d[k])
{
curr = curr * 20 + c[k];
foundr = true;
break;
}
else
++curr;
std::pair<int, int> tmp = now[i];
if (found)
{
tmp.first -= 1;
tmp.second -= cur;
}
if (foundr)
{
tmp.first += 1;
tmp.second += curr;
}
best[i] = std::min(best[i], tmp, cmp);
d[*p] ^= true;
}
p = std::find_if(e[i][j].begin(), e[i][j].end(), [&](const int &X)
{ return d[X]; });
if (p != e[i][j].end())
{
d[*p] ^= true;
int curr = 0;
bool foundr = false;
for (auto k : e[i][j])
if (d[k])
{
curr = curr * 20 + c[k];
foundr = true;
break;
}
else
++curr;
std::pair<int, int> tmp = now[i];
if (found)
{
tmp.first -= 1;
tmp.second -= cur;
}
if (foundr)
{
tmp.first += 1;
tmp.second += curr;
}
worst[i] = std::max(worst[i], tmp, cmp);
d[*p] ^= true;
}
}
}
max[0] = {114514, 0};
for (std::size_t i = 0; i != map.size(); ++i)
{
pp[i + 1] = pp[i];
max[i + 1] = max[i];
if (worst[i].first == 0)
pp[i + 1] = true;
else
max[i + 1] = std::max(max[i], worst[rk[i]], cmp);
}
for (std::size_t i = 0; i != map.size(); ++i)
{
int tr = std::lower_bound(rk, rk + map.size(), now[rk[i]], [&](const int &A, const std::pair<int, int> &B)
{ return cmp(now[A], B); }) -
rk;
bool flag = false;
// std::cout << f[rk[i]] << ' ' << max[i].first << ' ' << max[i].second << ' ' << now[rk[i]].first << ' ' << now[rk[i]].second << ' ' << pp[i] << std::endl;
if (!cmp(max[tr], now[rk[i]]))
flag |= tr - 1 < std::min((m + 9) / 10, 35);
if (pp[tr])
flag |= tr - 1 < std::min((m + 8) / 10, 35);
int nr = std::lower_bound(rk, rk + map.size(), best[rk[i]], [&](const int &A, const std::pair<int, int> &B)
{ return cmp(now[A], B); }) -
rk;
flag |= nr < std::min((m + 9 + (now[rk[i]].first == 0)) / 10, 35);
if (~addtim)
flag |= tr + cmp(std::pair<int, int>(1, addtim), now[rk[i]]) < std::min((m + 10) / 10, 35);
if (flag)
ans.push_back(rk[i]);
}
std::cout << ans.size() << std::endl;
for (std::size_t i = 0; i != ans.size(); ++i)
std::cout << f[ans[i]] << " \n"[i + 1 == ans.size()];
ans.clear();
for (std::size_t i = 0; i != map.size(); ++i)
{
now[i] = {0, 0};
for (int j = 0; j != 26; ++j)
e[i][j].clear();
}
map.clear();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 71320kb
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 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 4ms
memory: 72388kb
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: 4ms
memory: 68840kb
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 B C D E F G H I J K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 3ms
memory: 71896kb
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: 75ms
memory: 72680kb
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: 52ms
memory: 72272kb
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 tg buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU _Yej1PrINty...
result:
wrong answer the numbers are different in the case 33. (test case 33)