QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#629132	#9241. Sphinx	Zpair	28.5	228ms	5096kb	C++17	1.8kb	2024-10-11 05:44:20	2024-10-11 05:44:21

Judging History

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

[2024-10-11 05:44:21]
评测

测评结果：28.5
用时：228ms
内存：5096kb

查看

[2024-10-11 05:44:20]
提交

answer

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
//int perform_experiment(vector<int>E);
const int MAXN=255;
vector<int> e[MAXN];
struct DSU{
	int fa[MAXN];
	int find(int x){
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		fa[x]=y;
	}	
}a,b;
int NN,MM;
vector<int> XX,YY;
int get(vector<int> S){
	vector<int> op(NN);
	for(int i=0;i<NN;++i)
		b.fa[i]=i,op[i]=0;
	for(int x:S)op[x]=1;
	for(int i=0;i<MM;++i){
		int x=XX[i],y=YY[i];
		if(op[x]&&op[y])
			b.merge(x,y);
	}
	int cnt=0;
	for(int x:S)
		if(b.find(x)==x)
			++cnt;
	return cnt;
}
int cnt[MAXN],f[MAXN];
vector<int> find_colours(int N,vector<int>X,vector<int>Y) {
	NN=N,XX=X,YY=Y;
	int M=X.size();MM=M;
	for(int i=0;i<M;++i){
		e[X[i]].push_back(Y[i]);
		e[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<N;++i)
		a.fa[i]=i;
	vector<int> S;
	for(int i=1;i<N;++i)
		S.push_back(i);
	f[0]=1,cnt[0]=1+get(S);
	for(int i=1;i<N;++i){
		vector<int> now(N,N),S;
		for(int j=i+1;j<N;++j)
			S.push_back(j);
		for(int j=0;j<=i;++j)
			now[j]=-1;
		int ret=perform_experiment(now);
		int gt=get(S);
		if(ret==f[i-1]+1+gt){
			cnt[i]=f[i-1]+1+gt;
			f[i]=f[i-1]+1;
			continue;
		}
		int l=0,r=i-1,mid=(l+r)>>1;
		while(l<r){
			S.clear();
			for(int j=0;j<=mid;++j)
				now[j]=-1;
			for(int j=mid+1;j<i;++j)
				now[j]=N,S.push_back(j);
			now[i]=-1;
			for(int j=i+1;j<N;++j)
				now[j]=N,S.push_back(j);	
			ret=perform_experiment(now);
			if(ret==f[mid]+get(S))
				r=mid;
			else l=mid+1;
			mid=(l+r)>>1;
		}
		a.merge(i,l);
		S.clear();
		for(int j=i+1;j<N;++j)
			S.push_back(j);
		f[i]=f[i-1];
		cnt[i]=f[i]+get(S);
	}
	vector<int> ans(N);
	for(int i=0;i<N;++i)
		ans[i]=a.find(i);
	return ans;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1.5

Acceptable Answer

Test #1:

score: 3

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok #experiments: 1

Test #2:

score: 3

Accepted

time: 1ms

memory: 3832kb

input:

output:

result:

ok #experiments: 1

Test #3:

score: 1.5

Acceptable Answer

time: 0ms

memory: 3772kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 1.5

Acceptable Answer

time: 1ms

memory: 4064kb

input:

output:

result:

points 0.50 points  0.5

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3812kb

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

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3812kb

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

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3812kb

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

memory: 3812kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 1ms

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

score: 3.5

Acceptable Answer

time: 1ms

memory: 3816kb

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

memory: 3792kb

input:

output:

result:

points 0.50 points  0.5

Test #14:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3832kb

input:

output:

result:

points 0.50 points  0.5

Test #15:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3844kb

input:

output:

result:

points 0.50 points  0.5

Test #16:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3816kb

input:

output:

result:

points 0.50 points  0.5

Test #17:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4148kb

input:

output:

result:

points 0.50 points  0.5

Test #18:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4156kb

input:

output:

result:

points 0.50 points  0.5

Test #19:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3864kb

input:

output:

result:

points 0.50 points  0.5

Test #20:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3884kb

input:

output:

result:

points 0.50 points  0.5

Test #21:

score: 3.5

Acceptable Answer

time: 3ms

memory: 4148kb

input:

output:

result:

points 0.50 points  0.5

Test #22:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #23:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #24:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3872kb

input:

output:

result:

points 0.50 points  0.5

Test #25:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4112kb

input:

output:

result:

points 0.50 points  0.5

Test #26:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3804kb

input:

output:

result:

points 0.50 points  0.5

Test #27:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3764kb

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

Wrong Answer

time: 2ms

memory: 3880kb

input:

output:

result:

wrong answer Vertices 24 and 41 do have the same color, but they do not in returned answer

Subtask #3:

score: 16.5

Acceptable Answer

Test #34:

score: 16.5

Acceptable Answer

time: 31ms

memory: 3860kb

input:

output:

result:

points 0.50 points  0.5

Test #35:

score: 16.5

Acceptable Answer

time: 21ms

memory: 3860kb

input:

output:

result:

points 0.50 points  0.5

Test #36:

score: 16.5

Acceptable Answer

time: 25ms

memory: 4156kb

input:

output:

result:

points 0.50 points  0.5

Test #37:

score: 16.5

Acceptable Answer

time: 36ms

memory: 3804kb

input:

output:

result:

points 0.50 points  0.5

Test #38:

score: 16.5

Acceptable Answer

time: 32ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #39:

score: 16.5

Acceptable Answer

time: 21ms

memory: 3856kb

input:

output:

result:

points 0.50 points  0.5

Test #40:

score: 16.5

Acceptable Answer

time: 10ms

memory: 3824kb

input:

output:

result:

points 0.50 points  0.5

Test #41:

score: 16.5

Acceptable Answer

time: 31ms

memory: 3932kb

input:

output:

result:

points 0.50 points  0.5

Test #42:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3860kb

input:

output:

result:

points 0.50 points  0.5

Subtask #4:

score: 10.5

Acceptable Answer

Test #43:

score: 10.5

Acceptable Answer

time: 208ms

memory: 4784kb

input:

output:

result:

points 0.50 points  0.5

Test #44:

score: 10.5

Acceptable Answer

time: 179ms

memory: 4912kb

input:

output:

result:

points 0.50 points  0.5

Test #45:

score: 10.5

Acceptable Answer

time: 203ms

memory: 4904kb

input:

output:

result:

points 0.50 points  0.5

Test #46:

score: 10.5

Acceptable Answer

time: 191ms

memory: 4872kb

input:

output:

result:

points 0.50 points  0.5

Test #47:

score: 10.5

Acceptable Answer

time: 128ms

memory: 5096kb

input:

output:

result:

points 0.50 points  0.5

Test #48:

score: 10.5

Acceptable Answer

time: 109ms

memory: 4836kb

input:

output:

result:

points 0.50 points  0.5

Test #49:

score: 10.5

Acceptable Answer

time: 70ms

memory: 4828kb

input:

output:

result:

points 0.50 points  0.5

Test #50:

score: 10.5

Acceptable Answer

time: 228ms

memory: 4844kb

input:

output:

result:

points 0.50 points  0.5

Test #51:

score: 10.5

Acceptable Answer

time: 24ms

memory: 4836kb

input:

output:

result:

points 0.50 points  0.5

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer