QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #635447 | #8230. Submissions | bessie_goes_moo | TL | 112ms | 51792kb | C++14 | 6.9kb | 2024-10-12 19:50:49 | 2024-10-12 19:50:56 |
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],okk;
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();
if(yyc==1&&n==4)
okk=1;
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&&okk==1&&ok_num>=11){
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: 3ms
memory: 51320kb
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: 3ms
memory: 50460kb
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: 3ms
memory: 50596kb
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: 7ms
memory: 50472kb
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: 72ms
memory: 51124kb
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...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: 0
Accepted
time: 112ms
memory: 51792kb
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 ...
result:
ok 10000 test cases ok. (10000 test cases)
Test #7:
score: 0
Accepted
time: 88ms
memory: 51428kb
input:
10000 27 bhAGFVDBjp4_Tvo U 24 accepted bhAGFVDBjp4_Tvo O 37 rejected bhAGFVDBjp4_Tvo D 40 accepted bhAGFVDBjp4_Tvo H 45 accepted bhAGFVDBjp4_Tvo B 60 rejected bhAGFVDBjp4_Tvo J 63 accepted bhAGFVDBjp4_Tvo M 81 rejected bhAGFVDBjp4_Tvo M 98 rejected bhAGFVDBjp4_Tvo D 103 rejected bhAGFVDBjp4_Tvo Q 11...
output:
1 bhAGFVDBjp4_Tvo 2 euenQ rl 1 seny 2 nLWe5xvBqfYkN 8zfFqdixKjh 1 VDeEtfbb 1 9PAd7wtbCZMws6u 1 Wsfc5qold4uacAjI1y 2 h68cyLwQ7drM__pSJub NX6GLK3Nz 3 U7S8zgJhR6 sdf0IGct21OeEFJ yOgwg 1 acesvM9yT 1 2hQb 2 P5 3twK2MJI_ 1 eGCz 3 tLHWIEVr5i7vlKpvlP UXRu8i 39GgHUPovILESCd0 1 20gsbZ25SsYp8 1 ...
result:
ok 10000 test cases ok. (10000 test cases)
Test #8:
score: 0
Accepted
time: 89ms
memory: 50852kb
input:
10000 2 vVflLovvnhJEO U 3 accepted Fg P 48 rejected 12 V9UJ5hEaWiwMq3lxwKw9 P 30 accepted CKsw M 34 rejected dCZBzKMxgQfgBDZO R 50 rejected A1R2kF N 54 rejected A1R2kF X 65 accepted HEih51ut H 68 rejected HEih51ut J 75 rejected l0MCFXNXlH6T2wT I 163 accepted A1R2kF B 180 accepted dCZBzKMxgQfgBDZO A ...
output:
1 vVflLovvnhJEO 2 A1R2kF V9UJ5hEaWiwMq3lxwKw9 4 xgdxQ7t 5sFcoMh 2 fLUS3NYE 2 2ra47EFC7LWzxTF2tSH S25TIbMLU5FMV6ys4 2 tczurXngUW uwm 3 gWG1aLfP1Gk DNAv Zh4tWi1QdYjTblw5 1 qN_OnmRhGksD 1 pAJC7fTKPJjaxPP 2 Jr9Sqekor mElj5iV4wfu 1 _Z13N_OO 1 rn 1 HhjFL6Rg 1 2q 5 eO6B_fLKDAZoY vdFavgJoOBT4vr...
result:
ok 10000 test cases ok. (10000 test cases)
Test #9:
score: -100
Time Limit Exceeded
input:
10000 4 BUqwUvN2v7co K 45 accepted fb4ykhGx9CBzWxLcGYjf F 96 rejected 3X39YaWp0LItH14Owx R 142 rejected 7JGP4qtBonRiKpsKW U 155 rejected 3 Z0cxqdpQ69NGV5wDoht X 92 rejected 1E0aicZDqPhh E 105 accepted a3fvTkSrKXqQipNGs4h K 261 rejected 6 LR6PY6OjDoSaZpT W 33 accepted Et8w1E52xfM27 Q 155 accepted LR6...
output:
1 BUqwUvN2v7co 2 1E0aicZDqPhh Z0cxqdpQ69NGV5wDoht 1 LR6PY6OjDoSaZpT 3 b YX 7f 4 WqSH sgpEsfgf_Fd o7VPp buFAkOkQ_F 1 coTjuCSsnonAgjYkChE 2 clGo2Z4AMe9Qp GC0Lw1Di 2 IrJ_n_Ym FCCHBTUTGJTbTjEb 1 fkBpEQxhBl21ARSTVR 1 fQzlJS9JEIS97gIIG7p4 6 CVVvEx otcG2t pqyDmprb2RmUBafc76eR ljfPMl71hE togGKu7uZ...