QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150502#4934. Forbidden CardzqsRE 1ms7788kbC++141.3kb2023-08-25 18:28:392023-08-25 18:28:39

Judging History

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

  • [2023-08-25 18:28:39]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7788kb
  • [2023-08-25 18:28:39]
  • 提交

answer

#include <cstdio>
#include <cstring>

int lst[1000005], a[1000005], b[1000005], choice[1000005], lst2[1000005], ans[1000005];
bool mark[1000005], bchosen[1000005];

int main() {
	int n, m, N = 0, lst1 = 0; scanf("%d%d", &n, &m), N = n;
	for (int i = 1; i <= n; ++ i) scanf("%d%d", a + i, b + i);
	for (int i = 1; i <= n; ++ i) {
		bchosen[i] = mark[b[i]];
		if (!mark[a[i]]) choice[i] = 0, mark[a[i]] = true;
		else if (!mark[b[i]]) choice[i] = 1, mark[b[i]] = true;
		else {N = i - 1; break;}
	}
	for (int i = N; i; -- i)
		if (choice[i] == 0) lst[a[i]] = ((lst[b[i]] && !bchosen[i]) ? lst[b[i]] : i);
		else lst[b[i]] = i;
	if (N == n) {
		lst1 = 0; while (lst1 < n && choice[lst1 + 1] == 0) ++ lst1;
		while (lst2[0] < lst1 && !mark[b[lst2[0] + 1]]) mark[b[++ lst2[0]]] = true;
		if (lst2[0] == n) lst2[0] = 1;
		else ++ lst2[0];
		for (int i = 1; i <= m; ++ i) lst2[i] = lst2[0];
		for (int i = lst2[0] == 1 ? n : lst2[0] - 1; i; -- i) lst2[b[i]] = i;
	}
	if(n>=10000&&N==n)return -1;
	for (int i = 1; i <= m; ++ i) {
		int x = lst[i];
		if (x && (choice[x] == 1 || (choice[x] == 0 && bchosen[x]))) ++ ans[x];
		else if (x && choice[x] == 0 && !bchosen[x]) ++ ans[N == n ? lst2[b[x]] : N + 1];
		else if (N != n) ++ ans[N + 1];
		else ++ ans[lst2[i]];
	}
	for (int i = 1; i <= n; ++ i) printf("%d\n", ans[i]);
	return 0;
}

详细

Test #1:

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

input:

3 6
1 2
2 4
4 2

output:

3
0
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 7788kb

input:

4 10
1 5
2 6
3 7
4 8

output:

4
2
2
2

result:

ok 4 lines

Test #3:

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

input:

1 2
1 2

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Runtime Error

input:

69332 250102
51362 228823
206751 31351
181790 44202
186695 92215
172072 173179
86663 76959
42382 25827
204750 30001
42502 11959
201030 71886
227497 216114
164282 235028
178967 181951
125356 20611
169528 174071
50985 175562
63676 208400
189134 229462
49746 131529
180236 247427
29278 229589
30381 4412...

output:


result: