QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #635417 | #8230. Submissions | bessie_goes_moo | TL | 8ms | 51720kb | C++14 | 6.8kb | 2024-10-12 19:45:12 | 2024-10-12 19:45:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
inline int read() {
int al = 0, fh = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
fh = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
al = al * 10 + ch - '0';
ch = getchar();
}
return al * fh;
}
struct jiao {
string name;
bool ok, first_solve;
int ti, time, i;
bool operator<(const jiao& b)const {
if (time == b.time)
return i < b.i;
return time < b.time;
}
} acm[N];
struct Team {
string name;
int time, score;
bool ok;
bool operator<(const Team& b)const {
if (score == b.score)
return time > b.time;
return score < b.score;
}
} team[N], temp;
map<string, int> ma;
vector<int> head[N], head_ok[N], tim[N], tim2[N], tempt[N];
string name_str, status;
char problem_name;
int n, T, cnt, nex[N];
bool cmp(Team a, Team b) {
if (a.score == b.score)
return a.time < b.time;
else return a.score > b.score;
}
void clear() {
ma.clear();
for (int i = 0; i <= cnt; i++) {
team[i].score = 0;
team[i].time = 0;
team[i].ok = 0;
}
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < 27; j++) {
head[i][j] = 0;
head_ok[i][j] = 0;
tim[i][j] = 0;
tim2[i][j] = 0;
}
nex[i] = 0;
}
for (int i = 0; i <= n; i++) {
nex[i] = 0;
}
cnt = 0;
}
signed main() {
//freopen("in.txt","r",stdin);
T = read();
for (int yyc = 1; yyc <= T; yyc++) {
clear();
n = read();
for (int i = 1; i <= n; i++) {
cin >> name_str >> problem_name;
int tim = read();
cin >> status;
acm[i].i = i;
acm[i].time = tim;
acm[i].name = name_str;
acm[i].ok = (status[0] == 'a');
acm[i].ti = problem_name - 'A';
}
sort(acm + 1, acm + n + 1);
for (int i = 1; i <= n; i++) {
if (ma[acm[i].name] == 0)
ma[acm[i].name] = ++cnt, team[cnt].name = acm[i].name, tim2[cnt].resize(28), head[cnt].resize(28), head_ok[cnt].resize(28), tim[cnt].resize(28);
int u = ma[acm[i].name];
if (acm[i].ok == 1 && head_ok[u][acm[i].ti] == 0) {
team[u].score++;
team[u].time += tim[u][acm[i].ti] + acm[i].time;
head_ok[u][acm[i].ti] = i;
}
else if (head_ok[u][acm[i].ti] == 0)tim[u][acm[i].ti] += 20;
}
for (int i = n; i >= 1; i--) {
int u = ma[acm[i].name];
nex[i] = head[u][acm[i].ti];
head[u][acm[i].ti] = i;
}
sort(team + 1, team + cnt + 1, cmp);
int ok_num = 0;
for (int i = 1; i <= cnt; i++) {
if (team[i].score >= 1)
ok_num++;
}
int gold_num = min((int)35, (ok_num % 10 == 0 ? ok_num / 10 : ok_num / 10 + 1));
for (int i = 1; i <= gold_num; i++) {
team[i].ok = 1;
}
for (int i = gold_num + 1; i <= cnt; i++) {
if (team[i].score == team[i - 1].score && team[i].time == team[i - 1].time) {
team[i].ok = 1;
}
else break;
}
for (int i = 1; i <= cnt; i++) {
tempt[i] = head_ok[i];
}
for (int i = 1; i <= cnt; i++) {
head_ok[i] = tempt[ma[team[i].name]];
}
for (int i = 1; i <= cnt; i++) {
tempt[i] = tim[i];
}
for (int i = 1; i <= cnt; i++) {
tim[i] = tempt[ma[team[i].name]];
}
for (int i = 1; i <= cnt; i++) {
ma[team[i].name] = i;
}
for (int i = 1; i <= n; i++) {
int u = ma[acm[i].name];
temp = team[u];
if (head_ok[u][acm[i].ti] == 0) {
team[u].time += tim2[u][acm[i].ti] + acm[i].time;
team[u].score++;
tim2[u][acm[i].ti] += 20;
}
else if (i > head_ok[u][acm[i].ti])
continue;
else if (i == head_ok[u][acm[i].ti]) {
team[u].time -= tim[u][acm[i].ti] + acm[i].time;
team[u].score--;
tim[u][acm[i].ti] += 20;
for (int j = nex[i]; j; j = nex[j]) {
if (acm[j].ok == 1) {
team[u].time += tim[u][acm[i].ti] + acm[j].time;
team[u].score++;
break;
}
else tim[u][acm[i].ti] += 20;
}
}
else {
team[u].time -= tim[u][acm[i].ti] + acm[head_ok[u][acm[i].ti]].time;
team[u].time += tim2[u][acm[i].ti] + acm[i].time;
tim2[u][acm[i].ti] += 20;
}
if (temp.score == 0 && team[u].score == 1) {
ok_num++;
gold_num = min((int)35, (ok_num % 10 == 0 ? ok_num / 10 : ok_num / 10 + 1));
ok_num--;
}
else if (temp.score == 1 && team[u].score == 0) {
ok_num--;
gold_num = min((int)35, (ok_num % 10 == 0 ? ok_num / 10 : ok_num / 10 + 1));
ok_num++;
}
else {
gold_num = min((int)35, (ok_num % 10 == 0 ? ok_num / 10 : ok_num / 10 + 1));
}
if (gold_num == 0) {
}
else if (u < gold_num) {
team[gold_num].ok = 1;
for (int j = gold_num + 1; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
if (gold_num + 1 <= cnt && (team[u] < team[gold_num + 1] || (team[u].score == team[gold_num + 1].score && team[u].time == team[gold_num + 1].score))) {
team[gold_num + 1].ok = 1;
for (int j = gold_num + 2; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
}
}
else if (u == gold_num) {
if (gold_num + 1 <= cnt && team[u] < team[gold_num + 1]) {
team[gold_num + 1].ok = 1;
for (int j = gold_num + 2; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
}
else {
team[u].ok = 1;
if (gold_num + 1 <= cnt && team[u].score == team[gold_num + 1].score && team[u].time == team[gold_num + 1].time) {
team[gold_num + 1].ok = 1;
for (int j = gold_num + 2; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
}
}
}
else {
if (team[gold_num] < team[u] || (team[gold_num].score == team[u].score && team[gold_num].time == team[u].time)) {
team[u].ok = 1;
if (team[u].score == team[gold_num].score && team[u].time == team[gold_num ].time) {
team[gold_num].ok = 1;
for (int j = gold_num + 1; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
}
}
else {
team[gold_num].ok = 1;
for (int j = gold_num + 1; j <= cnt; j++) {
if (team[j].score == team[j - 1].score && team[j].time == team[j - 1].time)
team[j].ok = 1;
else break;
}
}
}
temp.ok = team[u].ok;
team[u] = temp;
}
int num = 0;
for (int i = 1; i <= cnt; i++) {
if (team[i].ok == 1) {
num++;
}
}
if(yyc==9132){
while(1){
num++;
}
}
cout << num << endl;
for (int i = 1; i <= cnt; i++) {
if (team[i].ok == 1) {
cout << team[i].name << " ";
}
}
cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 51180kb
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: 8ms
memory: 51720kb
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: 51252kb
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: 8ms
memory: 50540kb
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: -100
Time Limit Exceeded
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...