QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415668#7362. 割juan_1230 117ms12476kbC++14630b2024-05-21 08:35:232024-11-23 17:00:32

Judging History

你现在查看的是测评时间为 2024-11-23 17:00:32 的历史记录

  • [2024-11-23 17:00:50]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:128ms
  • 内存:12480kb
  • [2024-11-23 17:00:32]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:117ms
  • 内存:12476kb
  • [2024-05-21 08:35:23]
  • 评测
  • 测评结果:0
  • 用时:115ms
  • 内存:12684kb
  • [2024-05-21 08:35:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int ok[100005];
vector<int>p[200005];
int n,m;
const int M = 1000000;
int ans = 0;
signed main(){
	cin >> n >> m;
	for(int i = 1;i<=m;i++){
		int a,b;cin >>a  >> b;
		p[a].push_back(b),p[b].push_back(a);
	}
	for(int i = 0;i<M;i++){
		if(ans>=(m+1)/2)break;
		int now = rnd()%n+1,tt = 0,ww;
		for(int x:p[now])tt+=(ok[x]==ok[now]),ww+=(ok[x]!=ok[now]);
		if(tt>ww){
			ok[now]^=1;ans = ans-ww+tt;
		}
	}
	//cout << ans << endl;
	for(int i = 1;i<=n;i++)cout << ok[i] << ' ';cout<< endl;
	return 0;
}/*
4 6
1 2
1 3
1 4
2 3
2 4
3 4
*/

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 36ms
memory: 10128kb

input:

16 195777
7 4
2 5
10 1
4 16
9 3
1 3
9 8
11 5
9 4
1 12
9 4
6 1
2 7
6 1
14 4
2 16
1 6
5 11
16 3
15 8
16 12
1 4
8 3
9 16
11 8
7 16
16 1
1 7
3 16
4 16
9 12
3 9
16 11
4 14
12 5
16 12
1 8
2 16
4 7
11 7
4 13
5 8
1 4
6 4
2 15
6 5
5 4
4 8
1 9
14 7
8 5
7 1
11 9
12 14
5 2
9 13
4 16
1 7
5 3
13 6
15 8
7 1
1 5
6 ...

output:

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 

result:

wrong answer Your solution is wrong!

Test #2:

score: 0
Wrong Answer
time: 26ms
memory: 10100kb

input:

18 157831
6 14
14 1
12 17
13 10
8 18
18 15
15 6
2 12
3 15
12 13
17 12
7 8
8 14
1 17
7 4
2 7
12 11
9 13
10 13
15 6
15 13
1 4
6 1
16 15
16 4
7 17
17 5
8 13
18 7
9 15
10 2
12 7
13 1
11 7
6 17
12 3
7 1
5 1
1 11
9 1
12 16
18 7
9 7
1 10
13 7
6 13
18 16
17 4
1 8
17 18
18 5
3 16
18 15
3 5
2 3
12 14
6 12
17 ...

output:

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer Your solution is wrong!

Test #3:

score: 0
Time Limit Exceeded

input:

19 198538
3 4
19 5
11 19
7 4
4 13
2 16
12 17
10 15
17 8
5 6
4 15
8 3
12 17
2 10
5 16
3 5
12 11
9 4
2 9
17 3
2 12
8 9
17 1
4 12
9 1
1 4
19 3
8 2
19 15
8 16
3 15
13 4
18 15
11 16
6 18
12 13
7 1
15 2
15 11
14 18
10 5
6 2
7 1
12 5
7 13
12 10
10 12
17 13
10 12
3 11
6 11
8 18
13 5
11 15
11 4
19 10
13 16
1...

output:


result:


Test #4:

score: 0
Wrong Answer
time: 117ms
memory: 12120kb

input:

83589 185404
43233 56681
3323 66360
73015 30450
53246 1899
78495 28463
53683 41361
69084 10045
74137 44389
62334 49623
80530 50173
40547 25069
50011 28064
11982 16598
38051 72169
60920 75346
15561 27129
15586 377
5254 42928
42181 29431
7640 39932
55204 20070
69987 19176
10794 76339
53208 17098
71742...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #5:

score: 0
Wrong Answer
time: 117ms
memory: 12260kb

input:

89606 189269
38986 50381
52944 21966
76438 76554
26245 36307
37556 65697
12403 88456
4276 23672
60127 77809
29339 73238
4985 18809
71698 84894
62958 87185
18137 9825
604 60020
39768 87394
74584 44463
38609 58296
14612 48625
86908 79587
2151 37614
47272 21206
83180 79226
77511 3510
69744 81504
29102 ...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #6:

score: 0
Wrong Answer
time: 84ms
memory: 12476kb

input:

97464 189549
53251 12158
81432 30655
10095 21770
84832 53850
97262 29895
46488 91881
17252 10769
51795 72927
17345 38319
76129 91725
22467 55018
6907 47653
41429 21232
91453 36452
82095 90201
79595 23937
96518 32359
24885 49205
60454 19597
15788 80825
8990 89800
89785 55912
60357 14318
12642 62541
3...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #7:

score: 0
Wrong Answer
time: 85ms
memory: 12216kb

input:

78481 194415
46092 61133
36226 8857
58328 21579
1393 19800
11105 29638
26132 63170
31475 12911
56125 75060
21007 31451
2879 48784
71502 40714
39031 70254
11276 1256
27927 63170
43672 117
38624 46951
53669 3096
55546 28297
44471 76465
76177 24888
27216 46166
35632 8323
48158 8139
36344 58236
7752 602...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #8:

score: 0
Wrong Answer
time: 91ms
memory: 12340kb

input:

82362 195975
3742 65961
5178 6770
15224 68674
68042 14663
73212 44298
36875 25866
32790 6372
23000 53401
43229 46662
55722 2656
71053 76740
6319 29299
63423 68621
71538 47098
77003 76530
3777 44939
65908 48166
15181 47784
12041 64370
51137 63848
12252 28219
68481 6821
51724 59828
46612 51082
45936 1...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #9:

score: 0
Wrong Answer
time: 81ms
memory: 12080kb

input:

81379 182841
56468 44868
53031 43223
14309 65690
40586 22789
12604 66347
47330 22208
57571 24404
63464 18262
25011 45667
16231 24698
71524 37304
34135 78382
12631 76042
2735 54607
65003 23334
75436 73990
65807 10768
28435 66699
35592 52725
66181 27623
29161 32647
59791 44444
17516 61276
57950 44110
...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!

Test #10:

score: 0
Wrong Answer
time: 87ms
memory: 12408kb

input:

91356 198560
71601 29245
47552 90107
57700 85176
2337 24599
43240 21000
61189 48015
52025 72430
30647 84579
42035 82292
58729 88305
14473 38629
77323 20684
52465 26152
33826 11367
53639 32806
43946 24220
30783 14226
89836 53714
35139 20177
8549 12231
52673 15018
803 45176
22484 31182
1598 68139
2570...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer Your solution is wrong!