QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#553319	#9241. Sphinx	JohnAlfnov^#	36	34ms	4120kb	C++17	2.2kb	2024-09-08 11:52:16	2024-09-08 11:52:16

Judging History

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

[2024-09-08 11:52:16]
评测

测评结果：36
用时：34ms
内存：4120kb

查看

[2024-09-08 11:52:16]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#include "sphinx.h"
#endif
#ifndef ONLINE_JUDGE
int a[1005],b[1005],cnt=0;
int perform_experiment(vector<int>E){
	printf("%d\n",++cnt);
	int sz=E.size();
	for(int i=0;i<sz;++i){
		b[i]=(E[i]==-1?a[i]:E[i]);
	}
	int ans=1;
	for(int i=0;i<sz-1;++i)ans+=(b[i]!=b[i+1]);
	return ans;
}
#endif
int n;
vector<int>C,G;
int query(int l,int r,int c,int m){
	for(int i=0;i<n;++i)C[i]=c;
	for(int i=l;i<=r;++i)C[2*i+m]=-1;
	return perform_experiment(C);
}
void solve(int l,int r,vector<int>g,int m,int yj=0){
	if(l>r)return;
	if(l==r){
		if((signed)g.size()>1){
			for(auto c:g){
				int a=query(l,r,c,m);
				if(a==1){
					G[2*l+m]=c;
					break;
				}
			}
		}else G[2*l+m]=g[0];
		return;
	}
	int mid=(l+r)>>1;
	vector<int>g1,g2;
	for(auto c:g){
		if((signed)g1.size()==mid-l+1){
			if(yj){
				g2.emplace_back(c);
				continue;
			}
			int b=query(mid+1,r,c,m);
			if(b!=2*(r-mid)+1-(2*r+m==n-1)){
				g2.emplace_back(c);
			}
			continue;
		}
		if((signed)g2.size()==r-mid){
			if(yj){
				g1.emplace_back(c);
				continue;
			}
			int a=query(l,mid,c,m);
			if(a!=2*(mid-l+1)+1-(2*l+m==0)){
				g1.emplace_back(c);
			}
			continue;
		}
		int a=query(l,mid,c,m);
		if(a!=2*(mid-l+1)+1-(2*l+m==0)){
			g1.emplace_back(c);
		}else if(yj){
			g2.emplace_back(c);
			continue;
		}
		int b=query(mid+1,r,c,m);
		if(b!=2*(r-mid)+1-(2*r+m==n-1)){
			g2.emplace_back(c);
		}
	}
	solve(l,mid,g1,m,1);
	solve(mid+1,r,g2,m,1);
}
vector<int>find_colours(int N,vector<int>X,vector<int>Y){
	n=N;
	C.resize(n);G.resize(n);
	vector<int>z1,z2;
	for(int i=0;i<n;++i){
		if(n<=3){
			z1.emplace_back(i);
			z2.emplace_back(i);
			continue;
		}
		int l=0,r=(n-1)/2;
		int a=query(l,r,i,0);
		if(a!=2*(r-l+1)+1-(2*l+0==0)-(2*r+0==n-1)){
			z1.emplace_back(i);
		}
		r=n/2-1;
		int b=query(l,r,i,1);
		if(b!=2*(r-l+1)+1-(2*l+1==0)-(2*r+1==n-1)){
			z2.emplace_back(i);
		}
	}
	solve(0,(n-1)/2,z1,0,1);
	solve(0,n/2-1,z2,1,1);
	return G;
}
#ifndef ONLINE_JUDGE
int main(){
	int n;
	cin>>n;
	mt19937 mt(1377);
	for(int i=0;i<n;++i)a[i]=mt()%n;
	auto ans=find_colours(n,{},{});
	for(int i=0;i<n;++i)assert(a[i]==ans[i]);
	return 0;
}
#endif

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

input:

output:

result:

ok #experiments: 2

Test #2:

score: 3

Accepted

time: 1ms

memory: 3824kb

input:

output:

result:

ok #experiments: 3

Test #3:

score: 3

Accepted

time: 1ms

memory: 3824kb

input:

output:

result:

ok #experiments: 3

Test #4:

score: 3

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok #experiments: 4

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 2ms

memory: 3756kb

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: 196

Test #6:

score: 7

Accepted

time: 0ms

memory: 4036kb

input:

output:

result:

ok #experiments: 204

Test #7:

score: 7

Accepted

time: 0ms

memory: 3800kb

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: 236

Test #8:

score: 7

Accepted

time: 2ms

memory: 3800kb

input:

output:

result:

ok #experiments: 237

Test #9:

score: 7

Accepted

time: 3ms

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: 278

Test #10:

score: 7

Accepted

time: 3ms

memory: 3812kb

input:

output:

result:

ok #experiments: 292

Test #11:

score: 7

Accepted

time: 0ms

memory: 4068kb

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: 362

Test #12:

score: 7

Accepted

time: 3ms

memory: 3884kb

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: 363

Test #13:

score: 0

Wrong Answer

time: 4ms

memory: 4108kb

input:

output:

result:

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

Subtask #3:

score: 33

Accepted

Test #34:

score: 33

Accepted

time: 7ms

memory: 3764kb

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: 1014

Test #35:

score: 33

Accepted

time: 18ms

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: 1046

Test #36:

score: 33

Accepted

time: 13ms

memory: 3816kb

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: 1159

Test #37:

score: 33

Accepted

time: 9ms

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: 1216

Test #38:

score: 33

Accepted

time: 21ms

memory: 3816kb

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: 1640

Test #39:

score: 33

Accepted

time: 29ms

memory: 3816kb

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: 2142

Test #40:

score: 33

Accepted

time: 25ms

memory: 3804kb

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: 2480

Test #41:

score: 33

Accepted

time: 12ms

memory: 3816kb

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: 996

Test #42:

score: 33

Accepted

time: 34ms

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: 2643

Subtask #4:

score: 0

Runtime Error

Test #43:

score: 0

Runtime Error

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:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted