QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#553864	#9241. Sphinx	JohnAlfnov	10	261ms	5120kb	C++17	4.6kb	2024-09-08 21:34:16	2024-09-08 21:34:16

Judging History

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

[2024-09-08 21:34:16]
评测

测评结果：10
用时：261ms
内存：5120kb

查看

[2024-09-08 21:34:16]
提交

answer

#include<bits/stdc++.h>
#define ONLINE_JUDGE
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,m;
vector<int>C,G;
int fa[255],u[100005],v[100005];
int findfather(int x){
	return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
int aa[255];
int findaa(int x){
	return x==aa[x]?x:aa[x]=findaa(aa[x]);
}
vector<int>gg[255];
int ss[255],vist[255],tt,I;
int query(int l,int r){
	for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=n;
	for(int i=l;i<=r;++i)for(auto cu:gg[ss[i]])vist[cu]=1,C[cu]=-1;
	vist[I]=1,C[I]=-1;
	for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
		int fu=findaa(u[i]),fv=findaa(v[i]);
		if(fu!=fv)aa[fu]=fv;
	}
	int cnt=0;
	for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
	return r-l+1+1+cnt-perform_experiment(C);
}
double ef=0.37;
void solve(int l,int r,int k){
	if(!k)return;
	if(l==r){
		fa[ss[l]]=I;
		return;
	}
	int mid=(l+r)>>1;
	int k1=query(l,mid);
	solve(l,mid,k1);
	solve(mid+1,r,k-k1);
}
int s1[255],s2[255];
vector<int>g[255];
int dep[255];
void dfs(int x){
	vist[x]=1;
	for(auto cu:g[x])if(!vist[cu]){
		dep[cu]=dep[x]+1;
		dfs(cu);
	}
}
int p[255],v1[255],v2[255],ss1[255],ss2[255];
int query1(int l,int r,int d){
	for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=d;
	for(int i=l;i<=r;++i)for(auto cu:gg[ss1[i]])vist[cu]=1,C[cu]=-1;
	for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
		int fu=findaa(u[i]),fv=findaa(v[i]);
		if(fu!=fv)aa[fu]=fv;
	}
	int cnt=0;
	for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
	return r-l+1+cnt-perform_experiment(C);
}
int query2(int l,int r,int d){
	for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=d;
	for(int i=l;i<=r;++i)for(auto cu:gg[ss2[i]])vist[cu]=1,C[cu]=-1;
	for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
		int fu=findaa(u[i]),fv=findaa(v[i]);
		if(fu!=fv)aa[fu]=fv;
	}
	int cnt=0;
	for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
	return r-l+1+cnt-perform_experiment(C);
}
void solve1(int l,int r,int d){
	if(l==r){
		G[ss1[l]]=d;v1[ss1[l]]=1;
		return;
	}
	int mid=min(r+0.0,l+(r-l)*ef);
	int f1=query1(l,mid,d);
	if(!f1){
		solve1(mid+1,r,d);
	}else{
		solve1(l,mid,d);
		if(query1(mid+1,r,d))solve1(mid+1,r,d);
	}
}
void solve2(int l,int r,int d){
	if(l==r){
		G[ss2[l]]=d;v2[ss2[l]]=1;
		return;
	}
	int mid=min(r+0.0,l+(r-l)*ef);
	int f1=query2(l,mid,d);
	if(!f1){
		solve2(mid+1,r,d);
	}else{
		solve2(l,mid,d);
		if(query2(mid+1,r,d))solve2(mid+1,r,d);
	}
}
vector<int>find_colours(int N,vector<int>X,vector<int>Y){
	n=N;m=X.size();
	C.resize(n);G.resize(n);
	for(int i=0;i<m;++i)u[i]=X[i],v[i]=Y[i];
	for(int i=0;i<n;++i)fa[i]=i;
	for(int i=0;i<n;++i)p[i]=i;
	mt19937 mt(137777);
	shuffle(p,p+n,mt);
	for(int x=1;x<n;++x){
		int i=p[x];
		I=i;
		for(int j=0;j<x;++j)gg[p[j]].clear();
		for(int j=0;j<x;++j){
			gg[findfather(p[j])].emplace_back(p[j]);
		}
		tt=0;
		for(int j=0;j<x;++j)if(gg[p[j]].size())ss[++tt]=p[j];
		solve(1,tt,query(1,tt));
	}
	for(int j=0;j<n;++j)gg[j].clear();
	for(int j=0;j<n;++j){
		gg[findfather(j)].emplace_back(j);
	}
	for(int i=0;i<n;++i)g[i].clear();
	for(int i=0;i<m;++i)if(findfather(u[i])!=findfather(v[i])){
		int fu=fa[u[i]],fv=fa[v[i]];
		g[fu].emplace_back(fv);
		g[fv].emplace_back(fu);
	}
	int r=findfather(0);
	for(int i=0;i<n;++i)vist[i]=0;
	dep[r]=0;dfs(r);
	int t1=0,t2=0;
	for(int i=0;i<n;++i)if(fa[i]==i){
		if(dep[i]%2)s1[++t1]=i;
		else s2[++t2]=i;
	}
	if(t1+t2==1){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j)G[j]=(j==0?-1:i);
			if(perform_experiment(G)==1){
				for(int j=0;j<n;++j)G[j]=i;
				break;
			}
		}
		return G;
	}
	for(int i=0;i<n;++i)v1[i]=v2[i]=0;
	for(int i=0;i<n;++i)p[i]=i;
	shuffle(p,p+n,mt);
	for(int dd=0;dd<n;++dd){
		int d=p[dd];
		int tt1=0,tt2=0;
		for(int i=1;i<=t1;++i)if(!v1[s1[i]]){
			ss1[++tt1]=s1[i];
		}
		for(int i=1;i<=t2;++i)if(!v2[s2[i]]){
			ss2[++tt2]=s2[i];
		}
		shuffle(ss1+1,ss1+tt1+1,mt);
		shuffle(ss2+1,ss2+tt2+1,mt);
		if(tt1&&query1(1,tt1,d))solve1(1,tt1,d);
		if(tt2&&query2(1,tt2,d))solve2(1,tt2,d);
	}
	for(int i=0;i<n;++i)G[i]=G[fa[i]];
	return G;
}
#ifndef ONLINE_JUDGE
int main(){
	int n=10;
	mt19937 mt(time(0));
	for(int i=0;i<n;++i)a[i]=mt()%n;
	vector<int>X(n-1),Y(n-1);
	for(int i=0;i<n-1;++i){
		X[i]=i,Y[i]=i+1;
	}
	auto ans=find_colours(n,X,Y);
	for(int i=0;i<n;++i)assert(a[i]==ans[i]);
	system("sphinx");
	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: 3832kb

input:

output:

result:

ok #experiments: 2

Test #2:

score: 3

Accepted

time: 1ms

memory: 4096kb

input:

output:

result:

ok #experiments: 4

Test #3:

score: 3

Accepted

time: 0ms

memory: 4096kb

input:

output:

result:

ok #experiments: 4

Test #4:

score: 3

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok #experiments: 3

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 2ms

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:

ok #experiments: 195

Test #6:

score: 7

Accepted

time: 1ms

memory: 3812kb

input:

output:

result:

ok #experiments: 258

Test #7:

score: 7

Accepted

time: 2ms

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:

ok #experiments: 269

Test #8:

score: 7

Accepted

time: 3ms

memory: 3812kb

input:

output:

result:

ok #experiments: 266

Test #9:

score: 7

Accepted

time: 3ms

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:

ok #experiments: 279

Test #10:

score: 7

Accepted

time: 2ms

memory: 3812kb

input:

output:

result:

ok #experiments: 307

Test #11:

score: 7

Accepted

time: 3ms

memory: 3768kb

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

Test #12:

score: 7

Accepted

time: 3ms

memory: 3896kb

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

Test #13:

score: 7

Accepted

time: 4ms

memory: 3852kb

input:

output:

result:

ok #experiments: 317

Test #14:

score: 7

Accepted

time: 0ms

memory: 3860kb

input:

output:

result:

ok #experiments: 271

Test #15:

score: 7

Accepted

time: 4ms

memory: 3824kb

input:

output:

result:

ok #experiments: 329

Test #16:

score: 7

Accepted

time: 4ms

memory: 3864kb

input:

output:

result:

ok #experiments: 376

Test #17:

score: 7

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok #experiments: 64

Test #18:

score: 7

Accepted

time: 1ms

memory: 3876kb

input:

output:

result:

ok #experiments: 242

Test #19:

score: 7

Accepted

time: 3ms

memory: 3804kb

input:

output:

result:

ok #experiments: 232

Test #20:

score: 7

Accepted

time: 4ms

memory: 4144kb

input:

output:

result:

ok #experiments: 291

Test #21:

score: 7

Accepted

time: 4ms

memory: 3884kb

input:

output:

result:

ok #experiments: 324

Test #22:

score: 7

Accepted

time: 4ms

memory: 3860kb

input:

output:

result:

ok #experiments: 338

Test #23:

score: 7

Accepted

time: 4ms

memory: 3952kb

input:

output:

result:

ok #experiments: 357

Test #24:

score: 7

Accepted

time: 2ms

memory: 3860kb

input:

output:

result:

ok #experiments: 395

Test #25:

score: 7

Accepted

time: 3ms

memory: 4116kb

input:

output:

result:

ok #experiments: 262

Test #26:

score: 7

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok #experiments: 332

Test #27:

score: 7

Accepted

time: 3ms

memory: 3816kb

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:

ok #experiments: 366

Test #28:

score: 7

Accepted

time: 3ms

memory: 4080kb

input:

output:

result:

ok #experiments: 306

Test #29:

score: 7

Accepted

time: 4ms

memory: 3908kb

input:

output:

result:

ok #experiments: 346

Test #30:

score: 7

Accepted

time: 4ms

memory: 3788kb

input:

output:

result:

ok #experiments: 263

Test #31:

score: 7

Accepted

time: 5ms

memory: 3880kb

input:

output:

result:

ok #experiments: 348

Test #32:

score: 7

Accepted

time: 1ms

memory: 3824kb

input:

output:

result:

ok #experiments: 107

Test #33:

score: 7

Accepted

time: 5ms

memory: 4152kb

input:

output:

result:

ok #experiments: 391

Subtask #3:

score: 0

Runtime Error

Test #34:

score: 33

Accepted

time: 28ms

memory: 4088kb

input:

output:

result:

ok #experiments: 1663

Test #35:

score: 33

Accepted

time: 28ms

memory: 3836kb

input:

output:

result:

ok #experiments: 1724

Test #36:

score: 33

Accepted

time: 34ms

memory: 4132kb

input:

output:

result:

ok #experiments: 1883

Test #37:

score: 33

Accepted

time: 30ms

memory: 3928kb

input:

output:

result:

ok #experiments: 1934

Test #38:

score: 33

Accepted

time: 35ms

memory: 3828kb

input:

output:

result:

ok #experiments: 2094

Test #39:

score: 33

Accepted

time: 35ms

memory: 3828kb

input:

output:

result:

ok #experiments: 2265

Test #40:

score: 33

Accepted

time: 45ms

memory: 3792kb

input:

output:

result:

ok #experiments: 2537

Test #41:

score: 33

Accepted

time: 21ms

memory: 3832kb

input:

output:

result:

ok #experiments: 1511

Test #42:

score: 0

Runtime Error

input:

output:

result:

Subtask #4:

score: 0

Runtime Error

Test #43:

score: 21

Accepted

time: 56ms

memory: 5024kb

input:

output:

result:

ok #experiments: 903

Test #44:

score: 21

Accepted

time: 115ms

memory: 4712kb

input:

output:

result:

ok #experiments: 1303

Test #45:

score: 21

Accepted

time: 145ms

memory: 5012kb

input:

output:

result:

ok #experiments: 1678

Test #46:

score: 21

Accepted

time: 191ms

memory: 4728kb

input:

output:

result:

ok #experiments: 1874

Test #47:

score: 21

Accepted

time: 209ms

memory: 4772kb

input:

output:

result:

ok #experiments: 2216

Test #48:

score: 21

Accepted

time: 241ms

memory: 4876kb

input:

output:

result:

ok #experiments: 2382

Test #49:

score: 21

Accepted

time: 261ms

memory: 5120kb

input:

output:

result:

ok #experiments: 2502

Test #50:

score: 21

Accepted

time: 19ms

memory: 4696kb

input:

output:

result:

ok #experiments: 309

Test #51:

score: 0

Runtime Error

input:

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted