QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #647114 | #8230. Submissions | AlphaZe | WA | 13ms | 72080kb | C++20 | 5.3kb | 2024-10-17 11:48:33 | 2024-10-17 11:48:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int M = 1e5 + 10, N = 25, inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7, p = 13331;
int m;
int penal[26];
bool ans[M];
int n;
struct Submit {
int t, s;
};
struct Grade {
int nm, t;
void clear() { nm = t = 0; }
bool operator < (const Grade &that) const {
if (nm == that.nm) return t < that.t;
return nm > that.nm;
}
bool operator == (const Grade &that) const {
return nm == that.nm && t == that.t;
}
};
struct Team {
char str[N];
vector<Submit> e[26];
int ac;
Grade g1, g2, g3, g4;
void ins() {
g1.clear(); memset(penal, 0, sizeof penal);
// puts("sb?1");
for (int i = 0; i < 26; ++i) {
if (ac >> i & 1) {
++g1.nm; // puts("sb?");
for (auto sub : e[i]) {
if (sub.s) {
g1.t += sub.t, penal[i] += sub.t;
break;
} else g1.t += 20, penal[i] += 20;
}
}
} // 初始成绩
g2 = g1;
for (int i = 0; i < 26; ++i) {
if (!(ac >> i & 1)) {
if (!e[i].empty()) {
Grade nowg = {g1.nm + 1, g1.t + e[i][0].t};
g2 = min(g2, nowg);
}
} else {
Grade nowg = {g1.nm, g1.t - penal[i] + e[i][0].t};
g2 = min(g2, nowg);
}
} // 改一个成绩后最优
g3 = g4 = g2;
for (int i = 0; i < 26; ++i) {
if (ac >> i & 1) {
int nowpenal = 0, times = 0;
for (auto sub : e[i]) {
if (!sub.s) nowpenal += 20;
else {
if (!times) {
nowpenal += 20; ++times;
} else {
nowpenal += sub.t; ++times; break;
}
}
}
if (times == 1) g3 = max(g3, {g1.nm - 1, g1.t - penal[i]});
else g4 = max(g4, {g1.nm, g1.t - penal[i] + nowpenal});
}
}
}
bool operator < (const Team &that) const {
if (g1 == that.g1) return max(that.g3, that.g4) < max(g3, g4);
return g1 < that.g1;
}
}nd[M];
int getgold(int x) {
if (x % 10 == 0) return min(x / 10, 35);
return min(x / 10 + 1, 35);
}
void work() {
m = read(); n = 0; map<ll, int> mp;
for (int i = 1; i <= m; ++i) {
char str[N];
scanf("%s", str + 1);
int len = strlen(str + 1); ll has = 0;
for (int j = 1; j <= len; ++j) has = (has * p + str[j]) % mod;
if (mp.find(has) == mp.end()) {
mp[has] = ++n;
for (int j = 1; j < N; ++j) nd[n].str[j] = str[j];
for (int j = 0; j < 26; ++j) nd[n].e[j].clear(); nd[n].ac = 0;
}
int idx = mp[has];
char problem = getchar();
while (problem < 'A' || problem > 'Z') problem = getchar();
int t = read();
char status = getchar();
while (status != 'r' && status != 'a') status = getchar();
int p = problem - 'A', s = status == 'a';
if (s == 1) nd[idx].ac |= 1 << p;
nd[idx].e[p].push_back({t, s});
// printf("nd[%d].e[%d].pb({%d, %d}); \n", idx, p, t, s);
while (status != '\n') status = getchar();
}
for (int i = 1; i <= n; ++i) {
nd[i].ins();
// printf("%s\n", nd[i].str + 1);
// printf("{%d, %d}, {%d, %d}, {%d, %d}, {%d, %d}; \n", nd[i].g1.nm, nd[i].g1.t, nd[i].g2.nm, nd[i].g2.t, nd[i].g3.nm, nd[i].g3.t, nd[i].g4.nm, nd[i].g4.t);
}
sort(nd + 1, nd + n + 1);
int nn = n;
for (int i = nn; i; --i)
if (!nd[i].g1.nm) nn = i - 1;
else break;
int gold = getgold(nn);
for (int i = 1; i <= n; ++i) ans[i] = 0;
for (int i = 1; i <= gold; ++i) ans[i] = 1;
for (int i = gold + 1; i <= n; ++i) {
int nown = nn + (nd[i].g1.nm == 0), nowgold = getgold(nown);
if (nd[i].g2 < nd[nowgold].g1 || nd[i].g2 == nd[nowgold].g1) ans[i] = 1;
}
bool tag = 0;
if (getgold(nn) != getgold(nn - 1)) tag = 1;
Grade tog = nd[1].g4; int id = 1;
for (int i = 1; i <= gold; ++i) {
Grade nowtog = nd[1].g4;
if (nd[1].g3.nm || (!tag)) nowtog = max(nowtog, nd[1].g3);
if (tog < nowtog) tog = nowtog, id = i;
}
tog = min(tog, nd[gold + 1].g1);
// printf("tog = {%d, %d}; \n", tog.nm, tog.t);
for (int i = gold + 1; i <= n; ++i) {
if (nd[i].g1 < tog || nd[i].g1 == tog) ans[i] = 1;
}
int ansnm = 0;
for (int i = 1; i <= n; ++i) ansnm += ans[i];
printf("%d\n", ansnm);
for (int i = 1; i <= n; ++i)
if (ans[i]) printf("%s ", nd[i].str + 1); putchar('\n');
}
int main() {
int Tt = read();
while (Tt--) work();
}
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 71800kb
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 XuejunXinyoudui1 AllWayTheNorth ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 72080kb
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: -100
Wrong Answer
time: 6ms
memory: 71784kb
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:
2 A K 1 A
result:
wrong answer the numbers are different in the case 1. (test case 1)