QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#833530	#9241. Sphinx	dongyc666	3	403ms	4832kb	C++17	4.6kb	2024-12-26 21:00:15	2024-12-26 21:00:16

Judging History

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

[2024-12-26 21:00:16]
评测

测评结果：3
用时：403ms
内存：4832kb

查看

[2024-12-26 21:00:15]
提交

answer

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int NR=300;
int n,m,c[NR],fa[NR],tot,cnt,opt[NR],ans[NR],nc[NR],color[NR];
vector<int>g[NR],buc[NR],G[NR],v1,v2;
#define pb emplace_back

void init(){
	for(int i=1;i<=n;i++)fa[i]=i;
	cnt=n;
}
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
void merge(int x,int y){
	x=get(x);y=get(y);
	if(x==y)return;
	fa[x]=y;cnt--;
}

void dfs(int id,int k){
	if(color[id])return;
	if(k==1)v1.pb(id);
	else v2.pb(id);
	color[id]=k;
	for(int x:G[id])dfs(x,k^3);
}

bool check(vector<int>idx,vector<int>lcy,int color){
	for(int i=1;i<=n;i++)opt[i]=1;
	for(int x:idx)opt[x]=0;
	init();
	for(int i=1;i<=n;i++)
		for(int x:g[i])
			if(opt[c[x]]==opt[c[i]]){
				if(opt[c[x]])merge(i,x);
				else if(c[i]==c[x])merge(i,x);
			}
	vector<int>arr;
	for(int i=1;i<=n;i++)
		if(opt[c[i]])arr.pb(color);
		else arr.pb(-1);
	int tmp=perform_experiment(arr);
//	printf("---color:%d cnt:%d %d\n",color,cnt,tmp);
//	for(int x:idx)printf("%d ",x);puts("");
//	for(int x:lcy)printf("%d ",x);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",get(i));puts("");
	return cnt!=tmp;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
	n=N;m=X.size(); 
	for(int i=0;i<m;i++)g[X[i]+1].pb(Y[i]+1),g[Y[i]+1].pb(X[i]+1);
	for(int i=1;i<=n;i++)c[i]=i-1;
	for(int i=1;i<=n;i++){
		vector<int>buc;
		for(int x:g[i])
			if(x<i)buc.pb(x);
		if(!buc.size())continue;
		sort(buc.begin(),buc.end());
		int L=0,R=buc.size()-1;
		while(L<=R){
			init();
			for(int j=1;j<=n;j++)opt[j]=-1;
			for(int j=L;j<=R;j++)opt[buc[j]]=1;
			opt[i]=1;
			for(int j=1;j<=n;j++)
				for(int x:g[j])
					if(opt[j]==opt[x]){
						if(opt[j]==-1)merge(j,x);
						else if(c[j]==c[x])merge(j,x);
					}
			vector<int>arr;
			for(int i=1;i<=n;i++)
				if(opt[i]==-1)arr.pb(n);
				else arr.pb(-1);
			int tmp=perform_experiment(arr);
			if(tmp==cnt)break;
			int l=L,r=R,res=-1;
			while(l<=r){
				int mid=(l+r)>>1;init();
				for(int j=1;j<=n;j++)opt[j]=-1;
				for(int j=L;j<=mid;j++)opt[buc[j]]=1;
				opt[i]=1;
				for(int j=1;j<=n;j++)
					for(int x:g[j])
						if(opt[j]==opt[x]){
							if(opt[j]==-1)merge(j,x);
							else if(c[j]==c[x])merge(j,x);
						}
				vector<int>arr;
				for(int i=1;i<=n;i++)
					if(opt[i]==-1)arr.pb(n);
					else arr.pb(-1);
				int tmp=perform_experiment(arr);
				if(tmp!=cnt)res=mid,r=mid-1;
				else l=mid+1; 
			}
			if(res==-1)break;
			else{
				int x=c[buc[res]];
				for(int j=1;j<=n;j++)
					if(c[j]==x)c[j]=i-1;
				L=res+1;
			}
		}
	}
	bool ok=1;
	for(int i=1;i<=n;i++)ok&=(c[i]==n-1);
	if(ok){
		int ans=0;
		for(int c=0;c<n;c++){
			init();
			for(int j=1;j<n;j++)opt[j]=-1;opt[n]=1;
			for(int j=1;j<=n;j++)
				for(int x:g[j])
					if(opt[j]==-1&&opt[x]==-1)merge(j,x);
			vector<int>arr;
			for(int i=1;i<=n;i++)
				if(opt[i]==1)arr.pb(-1);
				else arr.pb(c);
			int tmp=perform_experiment(arr);
			if(tmp!=cnt){
				ans=c;
				break;
			}
		}
		vector<int>arr;
		for(int i=1;i<=n;i++)arr.pb(ans);
		return arr;
	}
	for(int i=1;i<=n;i++)c[i]++,buc[c[i]].pb(i);
	for(int i=1;i<=n;i++)
		for(int x:g[i])if(c[i]!=c[x])G[c[i]].pb(c[x]);
	dfs(n,1);
//	for(int x:v1)printf("%d ",x);puts("");
//	for(int x:v2)printf("%d ",x);puts("");
	for(int i=0;i<n;i++){
		if(check(v1,v2,i)){
//			printf("1:%d\n",i);
			int L=0,R=v1.size()-1;
			while(L<=R){
				vector<int>b1,b2;
				for(int i=0;i<=R;i++)
					if(L<=i&&i<=R)b1.pb(v1[i]);
					else b2.pb(v1[i]);
				for(int x:v2)b2.pb(x);
				if(!check(b1,b2,i))break;
				int l=L,r=R,res=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					vector<int>b1,b2;
					for(int i=0;i<=R;i++)
						if(l<=i&&i<=r)b1.pb(v1[i]);
						else b2.pb(v1[i]);
					for(int x:v2)b2.pb(x);
					if(check(b1,b2,i))res=mid,r=mid-1;
					else l=mid+1;
				}
				if(res==-1)break;
				else{
					ans[v1[res]]=i;
					L=res+1;
				}
			}
		}
		if(check(v2,v1,i)){
//			printf("2:%d\n",i);
			int L=0,R=v2.size()-1;
			while(L<=R){
				vector<int>b1,b2;
				for(int i=0;i<=R;i++)
					if(L<=i&&i<=R)b2.pb(v2[i]);
					else b1.pb(v2[i]);
				for(int x:v1)b1.pb(x);
				if(!check(b2,b1,i))break;
				int l=L,r=R,res=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					vector<int>b1,b2;
					for(int i=0;i<=R;i++)
						if(l<=i&&i<=r)b2.pb(v2[i]);
						else b1.pb(v2[i]);
					for(int x:v1)b1.pb(x);
					if(check(b2,b1,i))res=mid,r=mid-1;
					else l=mid+1;
				}
				if(res==-1)break;
				else{
					ans[v2[res]]=i;
					L=res+1;
				}
			}
		}
	}
	vector<int>arr;
	for(int i=1;i<=n;i++)arr.pb(ans[c[i]]);
	return arr;
}

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: 0ms

memory: 3904kb

input:

output:

result:

ok #experiments: 3

Test #2:

score: 3

Accepted

time: 0ms

memory: 4140kb

input:

output:

result:

ok #experiments: 9

Test #3:

score: 3

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok #experiments: 9

Test #4:

score: 3

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok #experiments: 4

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 1ms

memory: 3840kb

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

Test #6:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3844kb

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3844kb

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:

points 0.50 points  0.5

Test #8:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3920kb

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3876kb

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:

points 0.50 points  0.5

Test #10:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4140kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 7ms

memory: 3908kb

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:

points 0.50 points  0.5

Test #12:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3820kb

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:

points 0.50 points  0.5

Test #13:

score: 0

Wrong Answer

time: 8ms

memory: 3832kb

input:

output:

result:

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

Subtask #3:

score: 0

Wrong Answer

Test #34:

score: 33

Accepted

time: 21ms

memory: 3936kb

input:

output:

result:

ok #experiments: 1001

Test #35:

score: 16.5

Acceptable Answer

time: 14ms

memory: 3936kb

input:

output:

result:

points 0.50 points  0.5

Test #36:

score: 16.5

Acceptable Answer

time: 20ms

memory: 3864kb

input:

output:

result:

points 0.50 points  0.5

Test #37:

score: 16.5

Acceptable Answer

time: 20ms

memory: 4164kb

input:

output:

result:

points 0.50 points  0.5

Test #38:

score: 16.5

Acceptable Answer

time: 22ms

memory: 4120kb

input:

output:

result:

points 0.50 points  0.5

Test #39:

score: 0

Wrong Answer

time: 55ms

memory: 3864kb

input:

output:

result:

wrong answer Vertices 184 and 185 do not have the same color, but they do in returned answer

Subtask #4:

score: 0

Wrong Answer

Test #43:

score: 21

Accepted

time: 403ms

memory: 4728kb

input:

output:

result:

ok #experiments: 2570

Test #44:

score: 0

Wrong Answer

time: 401ms

memory: 4832kb

input:

output:

result:

wrong answer Vertices 4 and 21 do not have the same color, but they do in returned answer

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted