QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#832973	#9241. Sphinx	dongyc666^#	5	7ms	4544kb	C++17	1.7kb	2024-12-26 11:31:19	2024-12-26 11:31:24

Judging History

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

[2024-12-26 11:31:24]
评测

测评结果：5
用时：7ms
内存：4544kb

查看

[2024-12-26 11:31:19]
提交

answer

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int NR=210;
int n,m,c[NR],fa[NR],tot,cnt,opt[NR];
vector<int>g[NR];
#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--;
}

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());
//		printf("i:%d\n",i);
//		for(int x:buc)printf("%d ",x);puts("");
		int L=0,R=buc.size()-1;
		while(L<=R){
			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);
						}
	//			printf("mid:%d cnt:%d\n",mid,cnt);
	//			for(int j=1;j<=n;j++)printf("%d ",opt[j]);puts("");
	//			for(int j=1;j<=n;j++)printf("%d ",get(j));puts("");
				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);
	//			printf("tmp:%d\n",tmp);
				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;
			}
		}
	}
	vector<int>ans;
	for(int i=1;i<=n;i++)ans.pb(c[i]);
	return ans;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1.5

Acceptable Answer

Test #1:

score: 1.5

Acceptable Answer

time: 1ms

memory: 3884kb

input:

output:

result:

points 0.50 points  0.5

Test #2:

score: 3

Accepted

time: 1ms

memory: 4116kb

input:

output:

result:

ok #experiments: 1

Test #3:

score: 1.5

Acceptable Answer

time: 0ms

memory: 4072kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 3

Accepted

time: 0ms

memory: 4116kb

input:

output:

result:

ok #experiments: 1

Subtask #2:

score: 3.5

Acceptable Answer

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4072kb

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 #6:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4060kb

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3804kb

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

memory: 3888kb

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3828kb

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

memory: 3804kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3780kb

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

memory: 3824kb

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

Acceptable Answer

time: 0ms

memory: 4136kb

input:

output:

result:

points 0.50 points  0.5

Test #14:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4132kb

input:

output:

result:

points 0.50 points  0.5

Test #15:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Test #16:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3860kb

input:

output:

result:

points 0.50 points  0.5

Test #17:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3912kb

input:

output:

result:

points 0.50 points  0.5

Test #18:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3860kb

input:

output:

result:

points 0.50 points  0.5

Test #19:

score: 3.5

Acceptable Answer

time: 6ms

memory: 3856kb

input:

output:

result:

points 0.50 points  0.5

Test #20:

score: 3.5

Acceptable Answer

time: 5ms

memory: 3848kb

input:

output:

result:

points 0.50 points  0.5

Test #21:

score: 3.5

Acceptable Answer

time: 5ms

memory: 3912kb

input:

output:

result:

points 0.50 points  0.5

Test #22:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #23:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3848kb

input:

output:

result:

points 0.50 points  0.5

Test #24:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4144kb

input:

output:

result:

points 0.50 points  0.5

Test #25:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3760kb

input:

output:

result:

points 0.50 points  0.5

Test #26:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4076kb

input:

output:

result:

points 0.50 points  0.5

Test #27:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3872kb

input:

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

output:

result:

points 0.50 points  0.5

Test #28:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4120kb

input:

output:

result:

points 0.50 points  0.5

Test #29:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #30:

score: 3.5

Acceptable Answer

time: 7ms

memory: 3792kb

input:

output:

result:

points 0.50 points  0.5

Test #31:

score: 3.5

Acceptable Answer

time: 6ms

memory: 3924kb

input:

output:

result:

points 0.50 points  0.5

Test #32:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #33:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3880kb

input:

output:

result:

points 0.50 points  0.5

Subtask #3:

score: 0

Wrong Answer

Test #34:

score: 0

Wrong Answer

time: 0ms

memory: 4092kb

input:

output:

877694082

result:

wrong answer Invalid length of E

Subtask #4:

score: 0

Wrong Answer

Test #43:

score: 0

Wrong Answer

time: 7ms

memory: 4544kb

input:

output:

877694082

result:

wrong answer Invalid length of E

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer

Dependency #2:

50%

Acceptable Answer