QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #547051 | #8230. Submissions | ucup-team4821# | WA | 4ms | 11812kb | C++20 | 6.6kb | 2024-09-04 17:33:28 | 2024-09-04 17:33:28 |
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];
if (worst[i].first == 0)
pp[i + 1] = true;
else
max[i + 1] = std::max(max[i], worst[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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 11752kb
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: 11768kb
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: 11812kb
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: -100
Wrong Answer
time: 4ms
memory: 9792kb
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)