QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634392#8230. Submissionsbessie_goes_mooWA 143ms27912kbC++147.0kb2024-10-12 17:12:462024-10-12 17:12:50

Judging History

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

  • [2024-10-12 17:12:50]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:27912kb
  • [2024-10-12 17:12:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 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 < 26; 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() {
	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(27), head[cnt].resize(27), head_ok[cnt].resize(27), tim[cnt].resize(27);
			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 (u < gold_num) {
				if (team[gold_num].ok == 0) {
					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))) {
					if (team[gold_num + 1].ok == 0) {
						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]) {
					if (team[gold_num + 1].ok == 0) {
						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 == 0) {
						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 == 0) {
						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 {
					if (team[gold_num].ok == 0) {
						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++;
			}
		}

		cout << num << endl;
		for (int i = 1; i <= cnt; i++) {
			if (team[i].ok == 1) {
				cout << team[i].name << " ";
			}
		}
		cout << endl;
	}
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 27276kb

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: 0ms
memory: 27648kb

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: 27092kb

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: 3ms
memory: 27088kb

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: 143ms
memory: 27912kb

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: -100
Wrong Answer
time: 89ms
memory: 27116kb

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:

wrong answer the numbers are different in the case 27. (test case 27)