QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #547385 | #8230. Submissions | ucup-team4821 | WA | 13ms | 69076kb | C++14 | 6.6kb | 2024-09-04 21:11:43 | 2024-09-04 21:11:44 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 69076kb
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:
TS1 114514 0 2 381 0 TSxingxing10 114514 0 1 83 1 aoliaoligeiliao 114514 0 1 98 1 2 TS1 TSxingxing10 AllWayTheNorth 114514 0 2 514 0 XuejunXinyoudui1 1 264 2 514 0 LetItRot 1 264 2 514 1 ImYourFan 1 299 2 514 1 YaoYaoLingXian 1 299 1 10 1 4 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
result:
wrong output format Expected integer, but "TS1" found (test case 1)