QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328775#8230. Submissionsyan_silvaTL 919ms117340kbC++202.9kb2024-02-16 06:26:152024-02-16 06:26:16

Judging History

你现在查看的是最新测评结果

  • [2024-05-20 23:50:57]
  • hack成功,自动添加数据
  • (/hack/623)
  • [2024-05-20 23:48:44]
  • hack成功,自动添加数据
  • (/hack/622)
  • [2024-02-16 06:26:16]
  • 评测
  • 测评结果:TL
  • 用时:919ms
  • 内存:117340kb
  • [2024-02-16 06:26:15]
  • 提交

answer

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

void solve() {
	int n; cin>>n;

	map<string, vector<vector<int>>> ac, wa;
	vector<tuple<string, int, int, bool>> ev;
	for (int i = 0; i < n; i++) {
		string c, s; char p; int t;
		cin>>c>>p>>t>>s;
		if (!ac.count(c)) {
			ac[c].resize(26);
			wa[c].resize(26);
		} 

		bool is_ac = (s == "accepted");
		if (is_ac) {
			ac[c][p-'A'].push_back(i);
		} else {
			wa[c][p-'A'].push_back(i);
		}
		ev.emplace_back(c, p-'A', t, is_ac);
	}

	auto get_penalty = [&](string s, char c, int t) {
		int lb = lower_bound(all(wa[s][c]), t) - wa[s][c].begin();
		return get<2>(ev[t]) + lb*20;
	};

	int sz = 0;
	map<string, pair<int,int>> val;
	set<tuple<int, int, string>> teams;
	for (auto [c, v]: ac) {
		int num = 0, time = 0;
		for (int i = 0; i < 26; i++) {
			if (v[i].size()) {
				num++;
				time += get_penalty(c, i, v[i][0]);
			} 
		}
		val[c] = {-num, time};
		teams.emplace(-num, time, c);
		if (num) sz++;
	}

	auto get_top_size = [&sz]() {
		return min(35LL, (sz+9)/10);
	};

	set<string> res;
	auto update = [&]() {
		int top = get_top_size(), prv_num = 1, prv_time = 1;
		for (auto [num, time, c]: teams) {
			if (top <= 0) {
				if (num != prv_num or time != prv_time) break;
			} 
			res.insert(c);
			top--;
			prv_num = num, prv_time = time;
		}
	};

	update();
	for (int i = 0; i < n; i++) {
		auto [c, p, t, is_ac] = ev[i];

		auto [num, time] = val[c];
		teams.erase({num, time, c});

		int sv_sz = sz, new_num = -num, new_time = time;
		if (is_ac) {
			if (ac[c][p][0] == i) {
				if (ac[c][p].size() > 1) {
					new_time = new_time - get_penalty(c, p, i) + get_penalty(c, p, ac[c][p][1]) + 20;
				} else {
					// nao tenho mais ac na questao atual
					new_num--;
					new_time = new_time - get_penalty(c, p, i);
					if (new_num == 0) sz--;
				}
			}
		} else {
			if (ac[c][p].size()) {
				// ja tinha ac na questao
				// se o ac for depois
				// entao quero remover a penalidade dele
				// e adicionar a do atual
				if (i < ac[c][p][0]) {
					new_time = new_time - get_penalty(c, p, ac[c][p][0]) + get_penalty(c, p, i);
				}
			} else {
				// nao tinha nenhum ac
				new_num++;
				new_time = new_time + get_penalty(c, p, i);
				if (new_num == 1) sz++;
			}
		}

		teams.insert({-new_num, new_time, c});
		update();
		teams.erase({-new_num, new_time, c});

		teams.insert({num, time, c});
		sz = sv_sz;
	}

	cout<<res.size()<<'\n';
	for (auto c: res) cout<<c<<' '; cout<<'\n';
}

signed main() {
	fastio;
	int tt; cin>>tt;
	while (tt--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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 ImYourFan LetItRot XuejunXinyoudui1 

result:

ok 2 test cases ok. (2 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3636kb

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 jiangly_fan 
1
conqueror_of_tourist 

result:

ok 2 test cases ok. (2 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3544kb

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: 1ms
memory: 3576kb

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: 101ms
memory: 3628kb

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: 145ms
memory: 3600kb

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 tsd xiLm0TUOF3T 
2
JP t3 
2
77sgqpbTIr_Zt1 fhYPGC8W82NwJTQL 
2
3BQ pVWDEz 
2
buCeoOotAkV8DaFD6 tg 
1
UkXQ3iaNJ 
2
ALTqPt7JUSLrl vwfw 
1
QTEzV6tp 
3
4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz wJlbqIU 
2
6mbCu5zA eiuF7a_ 
1
xy6QBr8ECi 
3
PezeyUurYoz7N1iGU _Yej1PrINtydmO...

result:

ok 10000 test cases ok. (10000 test cases)

Test #7:

score: 0
Accepted
time: 169ms
memory: 3712kb

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
8zfFqdixKjh nLWe5xvBqfYkN 
1
VDeEtfbb 
1
9PAd7wtbCZMws6u 
1
Wsfc5qold4uacAjI1y 
2
NX6GLK3Nz h68cyLwQ7drM__pSJub 
3
U7S8zgJhR6 sdf0IGct21OeEFJ yOgwg 
1
acesvM9yT 
1
2hQb 
2
3twK2MJI_ P5 
1
eGCz 
3
39GgHUPovILESCd0 UXRu8i tLHWIEVr5i7vlKpvlP 
1
20gsbZ25SsYp8 
1
...

result:

ok 10000 test cases ok. (10000 test cases)

Test #8:

score: 0
Accepted
time: 157ms
memory: 3656kb

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
2 5sFcoMh fLUS3NYE xgdxQ7t 
2
2ra47EFC7LWzxTF2tSH S25TIbMLU5FMV6ys4 
2
tczurXngUW uwm 
3
DNAv Zh4tWi1QdYjTblw5 gWG1aLfP1Gk 
1
qN_OnmRhGksD 
1
pAJC7fTKPJjaxPP 
2
Jr9Sqekor mElj5iV4wfu 
1
_Z13N_OO 
1
rn 
1
HhjFL6Rg 
1
2q 
5
LjvEZmSkrsT QFFNJcyah90 eO6B...

result:

ok 10000 test cases ok. (10000 test cases)

Test #9:

score: 0
Accepted
time: 151ms
memory: 3592kb

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
7f YX b 
4
WqSH buFAkOkQ_F o7VPp sgpEsfgf_Fd 
1
coTjuCSsnonAgjYkChE 
2
GC0Lw1Di clGo2Z4AMe9Qp 
2
FCCHBTUTGJTbTjEb IrJ_n_Ym 
1
fkBpEQxhBl21ARSTVR 
1
fQzlJS9JEIS97gIIG7p4 
6
CVVvEx bLED4G7CY_M ljfPMl71hE otcG2t pqyDmprb2RmUBafc76...

result:

ok 10000 test cases ok. (10000 test cases)

Test #10:

score: 0
Accepted
time: 154ms
memory: 3648kb

input:

10000
7
dBv7DiT L 42 rejected
dBv7DiT P 123 accepted
7Bj2dZF6Gy7csrXYakI T 131 rejected
9KtuO O 190 accepted
BxACEk Q 285 rejected
BxACEk Q 291 rejected
HK0pq9qsGnlkgAQT L 296 accepted
3
NQgnW3CShrFJYkKdjagN G 53 rejected
ZwZCr O 261 accepted
ZwZCr P 270 accepted
6
mbGQ7wcZYr9leKBCsFN Z 4 rejected
7...

output:

2
9KtuO dBv7DiT 
1
ZwZCr 
2
4LUVnW93OFHOl6fJOmXK 7s1bgtS 
4
CZNz6k1QgLrHojbY _g2LouxyEI_BXaOYQWn pz upCvWQnHRgRSQQ 
3
q t ungF4dKzJt290JMWNgeH 
3
4FjAuM44Nzaz6Tc0 6mCVqSBpHVkrNZ SuBp7xLMGCHgk 
1
xXqqS7r1OU 
1
YEHiJvhHR8OmUWz 
3
0WZFvefoPtNo BiasA1Md2ViU m 
1
MzQD 
2
L501za_ktc MJJ4n2rC7YHRflGzEL 
1
...

result:

ok 10000 test cases ok. (10000 test cases)

Test #11:

score: 0
Accepted
time: 29ms
memory: 9672kb

input:

7
110
10 A 0 accepted
0 A 100 accepted
1 A 100 accepted
2 A 100 accepted
3 A 100 accepted
4 A 100 accepted
5 A 100 accepted
6 A 100 accepted
7 A 100 accepted
8 A 100 accepted
9 A 100 accepted
0 B 100 accepted
1 B 100 accepted
2 B 100 accepted
3 B 100 accepted
4 B 100 accepted
5 B 100 accepted
6 B 10...

output:

11
0 1 10 2 3 4 5 6 7 8 9 
11
0 1 10 2 3 4 5 6 7 8 9 
11
0 1 10 2 3 4 5 6 7 8 9 
11
0 1 100 2 3 4 5 6 7 8 9 
12
0 1 10 100 2 3 4 5 6 7 8 9 
36
0 1 10 11 12 13 14 15 16 17 18 19 2 20 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 4 5 6 7 8 9 
35
0 1 10 11 12 13 14 15 16 17 18 19 2 20 21 22 23 24 25 2...

result:

ok 7 test cases ok. (7 test cases)

Test #12:

score: 0
Accepted
time: 218ms
memory: 4152kb

input:

1000
58
8VR4968BiWGrjt0 G 1 accepted
KfduBOJVYor3ixLgzUo Y 5 accepted
r9l9P_xyc7oagiZS0ZJ G 26 accepted
PL3OrMzXRJRVskByRHHl Y 38 accepted
7wL2M4T1PWyv9rJSdzGN N 47 rejected
Vu56KH6ZGwSm E 48 rejected
8VR4968BiWGrjt0 D 53 accepted
SI7h8yP C 57 rejected
aSVEsYSH9PJjsjSAyH N 61 accepted
D3UrdM8xI S 71...

output:

5
8VR4968BiWGrjt0 PL3OrMzXRJRVskByRHHl SI7h8yP mn0iyGyqWOakTAs1Qw umqh9D 
6
3A4BJULiR9S 6OSsIJ 9M EYdAeGI f22a5ba_ze2qsm2_2k uxPAbOmdBcWg64Q52 
25
19Mbp 6zU 9DVkaj8vMDxLV4MVh2O_ 9sFtbGG4oMjSgmtZh D6SdnJFh6xFQlZehalkc DIt FJhecJwM JjWIyr8 OltMSo53IsdGRLoUb0 Qo8l4lQKg V XJ9p0AKseAnbt7vmR_ Zsl aaM4iPkd...

result:

ok 1000 test cases ok. (1000 test cases)

Test #13:

score: 0
Accepted
time: 359ms
memory: 7176kb

input:

100
974
qG R 0 accepted
k2K I 0 accepted
NelrCjQd_AHSw107 D 1 accepted
ybeH_JvdmCLMOGl9x K 1 accepted
h3 Q 2 accepted
9qOW O 2 accepted
v1IWHoW7Mkuce6qH Y 2 accepted
mlypVkK5Xl1KXw3o P 2 rejected
zs X 3 accepted
1Fpyq8oUYV_aNp I 3 rejected
e1bM8xUh E 3 rejected
myaSH0LCL4hD5BlAj F 4 rejected
IJETUS2...

output:

65
0NhoPE 185RryPWmjK2h47NJax 1qXXQyXNhDyf97IT0n 2cBZ 2tougTgqY91VXB3 3f3gDxR 55IlpzN 7DHKKRDYO 9qOW DO0tQAc FJ9Y Hy551D5ZPfvBDS IJETUS2jG Io5tMwXAJlbYL2Wikqqq JSC6wpny7viIbAUq LM5B LhlGfI4XZ Ms7FjfFm NelrCjQd_AHSw107 OZv7jP6ZP1L0pmwrtfW PGbK PlD7x1RoiUUo Q3wkiZxpn13i_s64Y QGg QW QXFitGeaPT8BjI T0nx...

result:

ok 100 test cases ok. (100 test cases)

Test #14:

score: 0
Accepted
time: 518ms
memory: 25288kb

input:

10
5371
r0JLpp2hFx T 0 accepted
w19l89 X 0 rejected
PeEB Y 0 accepted
2MwVQe3 Y 0 accepted
CarjodD8k4E K 0 accepted
vNjq0LmY D 0 accepted
Bvi16IvVACG3uREuoO X 0 accepted
yMlDlaWPTluR1dk43nl6 A 0 rejected
4LBA3qILgaib4lrQ X 1 accepted
vRSpyKVAU7e I 1 rejected
627aFcGG4zh8 Z 1 rejected
FHwI U 1 accept...

output:

85
2AF3LbCAMXg 2HT7G5q_UM4CH 2YL1K5JThyVh6 2q1QkMCewAeWl 3L 3ntTBJ2G 3oyR1q 4J8yfyWPQLaYwOPbQ1c 5gGJk 61F 7Ezg6 7R 9Saa 9al As_jBpG0uR9t CgcD1 DP3Q56WAbP DdOUBy DoLs Du2Rmmj_rlgveV EpqKVhDBeo4JaEWcz7 FHjsj6oWpg72iBLgjLf FHwI FlTsTqSJ Gthf5xZXaX6rY I9Tfaeo6lTwLkgC90n IxS JH8 KwjId5DA66 LENUDmAZjz8S6Q...

result:

ok 10 test cases ok. (10 test cases)

Test #15:

score: 0
Accepted
time: 919ms
memory: 117340kb

input:

1
100000
OZeDY6m2v P 0 accepted
DolcP A 0 accepted
2Z9Yd M 0 rejected
Vjl F 0 accepted
SPetC8_ru4S3nXJkkD C 0 rejected
XhLC G 0 rejected
wZvhcns7t7EaOero E 0 accepted
HRqRKcO87 I 0 rejected
dwfT7D H 0 rejected
cxvYaN8zSMGpoa9Q9xv U 0 accepted
nvXlrCa1zbx8uokfd T 0 accepted
E_bbU5C9bgpD_wGo P 0 rejec...

output:

213
0I6_zoHOMIlwLEAjxGA 0hELBpU5n_QXtw 0hH 0jTK9uR3FcSB 1T 1dH9n4ucH5tDCWoaEBXl 2bAcFJDTW9 2pY7Nw 2rzxtwkikpsE 3Pokt6fwaxOe9TjlAV 4Va0Qz3xegJa1YTzfwB 4dQZ7VRS3v8lyV 4rcv 5FfAavp 5Zuy37 6CTTfzkMmnDqDIP 6r0Uc4guMCP2kZU 6rxpy_f_0 6u 72oo 7DqC__BGQC70H0v 7XG 7aO76gOH3CfOnT0vsJqh 7ibHgbbm7tvPSzrCqmo 7rhb...

result:

ok 1 test cases ok. (1 test case)

Test #16:

score: 0
Accepted
time: 43ms
memory: 11360kb

input:

1
100000
A A 0 accepted
B Z 299 accepted
B Z 299 accepted
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A 299 rejected
B A ...

output:

1
B 

result:

ok 1 test cases ok. (1 test case)

Test #17:

score: -100
Time Limit Exceeded

input:

1
100000
qyGXWlwMuXY3212 A 20 accepted
l_IeEuuLy9 A 20 accepted
nlyFO0YOiDxyiNjBb A 20 accepted
8H A 20 accepted
ek A 20 accepted
Em63tewQVLljOUO4r A 20 accepted
AHdtZtwK8debApdvxMy8 A 20 accepted
l3aTB A 20 accepted
vyFuSSSLTV5yP A 20 accepted
uzPnnAXshwHCbl7 A 20 accepted
sL A 20 accepted
K099qoYV...

output:


result: