QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#833077	#9241. Sphinx	dongyc666^#	36	54ms	4300kb	C++17	1.3kb	2024-12-26 12:58:42	2024-12-26 12:58:43

Judging History

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

[2024-12-26 12:58:43]
评测

测评结果：36
用时：54ms
内存：4300kb

查看

[2024-12-26 12:58:42]
提交

answer

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
int n;
#define pb emplace_back
vector<int>ans;

int solve(int l,int r,int c){
	if(l>r)return 0;
	if(ans[l]!=n-1)return solve(l+2,r,c);
	if(ans[r]!=n-1)return solve(l,r-2,c);
	vector<int>arr(n,n);
	for(int i=l;i<=r;i+=2)arr[i]=-1;
	int L=((l>0)?(l-1):(l+1)),R=((r<n-1)?(r+1):(r-1));
	for(int i=L;i<=R;i+=2)arr[i]=c;
	L=min(L,l);R=max(R,r);
	int res=perform_experiment(arr);
	res-=(L>0);
	res-=(R<n-1);
	if(res==R-L+1)return 0;
	if(l==r){
		ans[l]=c;
		return l==0||l==n-1?1:2;
	}
	int mid=(l+r)>>1;
	mid-=((mid-l)&1);
	int res2=0;
	res2+=solve(l,mid,c);
	if(res2+res!=R-L+1)res2+=solve(mid+2,r,c);
	return res2;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
	n=N;ans.resize(n);
	for(int i=0;i<n;i++)ans[i]=n-1;
	if(n==2){
		for(int i=0;i<n-1;i++){
			vector<int>tmp;tmp.pb(-1);tmp.pb(i);
			int res=perform_experiment(tmp);
			if(res==1){
				ans[0]=i;
				break;
			}
		}
		for(int i=0;i<n-1;i++){
			vector<int>tmp;tmp.pb(i);tmp.pb(-1);
			int res=perform_experiment(tmp);
			if(res==1){
				ans[1]=i;
				break;
			}
		}
		return ans;
	}
	for(int i=0;i<n-1;i++)solve(0,n-1-((n-1)&1),i);
	for(int i=0;i<n-1;i++)solve(1,n-1-!((n-1)&1),i);
	return ans;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 1ms

memory: 3832kb

input:

output:

result:

ok #experiments: 2

Test #2:

score: 3

Accepted

time: 1ms

memory: 3784kb

input:

output:

result:

ok #experiments: 2

Test #3:

score: 3

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok #experiments: 2

Test #4:

score: 3

Accepted

time: 0ms

memory: 3808kb

input:

output:

result:

ok #experiments: 2

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 2ms

memory: 4028kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

ok #experiments: 146

Test #6:

score: 7

Accepted

time: 2ms

memory: 3776kb

input:

output:

result:

ok #experiments: 182

Test #7:

score: 7

Accepted

time: 2ms

memory: 3796kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

ok #experiments: 204

Test #8:

score: 7

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok #experiments: 198

Test #9:

score: 7

Accepted

time: 2ms

memory: 4112kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

ok #experiments: 216

Test #10:

score: 7

Accepted

time: 2ms

memory: 3808kb

input:

output:

result:

ok #experiments: 266

Test #11:

score: 7

Accepted

time: 3ms

memory: 3752kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

ok #experiments: 332

Test #12:

score: 7

Accepted

time: 0ms

memory: 4096kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

ok #experiments: 352

Test #13:

score: 0

Wrong Answer

time: 0ms

memory: 3820kb

input:

output:

result:

wrong answer Vertices 2 and 20 do not have the same color, but they do in returned answer

Subtask #3:

score: 33

Accepted

Test #34:

score: 33

Accepted

time: 8ms

memory: 3820kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 720

Test #35:

score: 33

Accepted

time: 10ms

memory: 4104kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 992

Test #36:

score: 33

Accepted

time: 18ms

memory: 3756kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 1015

Test #37:

score: 33

Accepted

time: 23ms

memory: 4120kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 1089

Test #38:

score: 33

Accepted

time: 21ms

memory: 3892kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 1393

Test #39:

score: 33

Accepted

time: 21ms

memory: 3812kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 1940

Test #40:

score: 33

Accepted

time: 36ms

memory: 3780kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2387

Test #41:

score: 33

Accepted

time: 6ms

memory: 3848kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 764

Test #42:

score: 33

Accepted

time: 54ms

memory: 4108kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

ok #experiments: 2659

Subtask #4:

score: 0

Wrong Answer

Test #43:

score: 0

Wrong Answer

time: 15ms

memory: 4300kb

input:

output:

877694080
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
-1
0
...

result:

wrong answer Vertices 0 and 3 do have the same color, but they do not in returned answer

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted