QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629117#9241. SphinxZpair1.5 30ms4572kbC++171.1kb2024-10-11 04:50:312024-10-11 04:50:32

Judging History

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

  • [2024-10-11 04:50:32]
  • 评测
  • 测评结果:1.5
  • 用时:30ms
  • 内存:4572kb
  • [2024-10-11 04:50:31]
  • 提交

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];
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;
}
int cnt[MAXN];
vector<int> find_colours(int N,vector<int>X,vector<int>Y) {
	int M=X.size();
	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)
		fa[i]=i;
	cnt[0]=1;
	for(int i=1;i<N;++i){
		vector<int> now(N,N);
		for(int j=0;j<=i;++j)
			now[j]=-1;
		int ret=perform_experiment(now);
		if(ret==cnt[i-1]+1){
			cnt[i]=cnt[i-1]+1;
			continue;
		}
		int l=0,r=i-1,mid=(l+r)>>1;
		while(l<r){
			for(int j=0;j<=mid;++j)
				now[j]=-1;
			for(int j=mid+1;j<i;++j)
				now[j]=N;
			now[i]=-1;
			for(int j=i+1;j<N;++j)
				now[j]=N;			
			ret=perform_experiment(now);
			if(ret==cnt[mid]+1)
				r=mid;
			else l=mid+1;
			mid=(l+r)>>1;
		}
		merge(i,l);
		cnt[i]=cnt[i-1];
	}
	vector<int> ans(N);
	for(int i=0;i<N;++i)
		ans[i]=find(i);
	return ans;
}

详细

Subtask #1:

score: 1.5
Acceptable Answer

Test #1:

score: 3
Accepted
time: 1ms
memory: 3800kb

input:

1978433568
2
1
0
1
1978433568
1

output:

877694080
-1
-1
877694081
0
0

result:

ok #experiments: 1

Test #2:

score: 3
Accepted
time: 1ms
memory: 4060kb

input:

1978433568
2
1
0
1
1978433568
2

output:

877694080
-1
-1
877694081
0
1

result:

ok #experiments: 1

Test #3:

score: 1.5
Acceptable Answer
time: 1ms
memory: 4092kb

input:

1978433568
2
1
0
1
1978433568
2

output:

877694080
-1
-1
877694081
0
1

result:

points 0.50 points  0.5

Test #4:

score: 1.5
Acceptable Answer
time: 0ms
memory: 3812kb

input:

1978433568
2
1
0
1
1978433568
1

output:

877694080
-1
-1
877694081
0
0

result:

points 0.50 points  0.5

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

50%
Acceptable Answer

Test #5:

score: 0
Wrong Answer
time: 2ms
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:

877694080
-1
-1
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
877694080
-1
-1
-1
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
5...

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 21ms
memory: 3820kb

input:

1978433568
250
249
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
49
50
...

output:

877694080
-1
-1
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #43:

score: 0
Wrong Answer
time: 30ms
memory: 4572kb

input:

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

output:

877694080
-1
-1
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
250
...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

50%
Acceptable Answer

Dependency #2:

0%