QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#569400#9321. Permutations and Cycles (Minimum Version)CrysflyAC ✓15ms13352kbC++143.0kb2024-09-16 22:37:222024-09-16 22:37:24

Judging History

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

  • [2024-09-16 22:37:24]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:13352kb
  • [2024-09-16 22:37:22]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define i128 __int128
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

struct ufs{
	int fa[maxn],sz[maxn];
	stack<pii>s;
	void init(int n){
		For(i,1,n)fa[i]=i,sz[i]=0;
		while(s.size())s.pop();
	}
	inline int getf(int x){while(x!=fa[x])x=fa[x];return x;}
	inline bool merge(int x,int y){
		x=getf(x),y=getf(y);
		if(x==y)return 0;
		if(sz[x]>sz[y])swap(x,y);
		s.push(mkp(x,sz[x]==sz[y]));
		fa[x]=y,sz[y]+=s.top().se;
		return 1;
	}
	inline bool chk(int x,int y){
		return getf(x)==getf(y);
	}
	void back(int t){
		while(s.size()>t){
			sz[fa[s.top().fi]]-=s.top().se;
			fa[s.top().fi]=s.top().fi;
			s.pop();
		}
	}
}U;

int n,k;

int l,r,p[maxn],ok;
void dfs(int u){
	if(l>r){
		ok=1;
		return;
	}
	int v=n-u+1;
	if(u==v){
		p[l]=u;
		ok=1;
		return;
	}
	// [v,u],....   or  ....,[u,v]
	p[l]=v,p[l+1]=u;
	int tim=U.s.size();
	if(U.merge(p[l],l)){
		if(r==l+1 || U.merge(p[l+1],l+1)){
//			cout<<"Addl "<<v<<" "<<u<<"\n";
			l+=2;
			dfs(u+1);
			if(ok)return;
			l-=2;
		}
	}
	U.back(tim);
	p[r]=v,p[r-1]=u;
	if(U.merge(p[r],r)){
		if(r==l+1 || U.merge(p[r-1],r-1)){
//			cout<<"Addr "<<u<<" "<<v<<" "<<r<<"\n";
//			For(i,1,n)cout<<p[i]<<" \n"[i==n];
			r-=2;
			dfs(u+1);
			if(ok)return;
			r+=2;
		}
	}
	U.back(tim);
}

bool vis[maxn];
int calc(){
	For(i,1,n)vis[i]=0;
	For(i,1,n){
		assert(p[i]>=1 && p[i]<=n);
		assert(!vis[p[i]]);
		vis[p[i]]=1;
	}
	int res=0;
	For(i,1,n)vis[i]=0;
	For(i,1,n)if(!vis[i]){
		for(int u=i;!vis[u];u=p[u])vis[u]=1;
		++res;
	}
	return res;
}
int q[maxn];

void work()
{
	n=read(),k=read();
	if(n==7){
		if(k==8){
			puts("2\n4 3 5 2 6 1 7");
		}else{
			puts("1\n2 7 1 6 3 5 4");
		}return;
		auto chk=[&](){
			For(i,1,n-1)if(p[i]+p[i+1]>k)return 0;
			return 1;
		};
		For(i,1,n)p[i]=i; int mn=n+1;
		do{
			if(!chk())continue;
			int tmp=calc();
			if(tmp<mn){
				mn=tmp;
				For(i,1,n)q[i]=p[i];
			}
		}while(next_permutation(p+1,p+n+1));
		cout<<mn<<"\n";
		For(i,1,n)cout<<q[i]<<" \n"[i==n];
		return;
	}
	U.init(n);
	ok=0; l=1,r=n;
	dfs(1);
	assert(ok);

	cout<<1<<"\n";
	For(i,1,n)cout<<p[i]<<" ";cout<<"\n";
	assert(calc()==1);
}

signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	int T=read();
	while(T--)work();
	return 0;
}
/*
brute
*/ 

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

2
2 3
6 10

output:

1
2 1 
1
6 1 5 2 4 3 

result:

ok ok

Test #2:

score: 0
Accepted
time: 4ms
memory: 7816kb

input:

6
32232 40040
7 8
7 9
7 10
7 11
7 12

output:

1
32232 1 32231 2 32230 3 32229 4 32228 5 32227 6 32226 7 32225 8 32224 9 32223 10 32222 11 32221 12 32220 13 32219 14 32218 15 32217 16 32216 17 32215 18 32214 19 32213 20 32212 21 32211 22 32210 23 32209 24 32208 25 32207 26 32206 27 32205 28 32204 29 32203 30 32202 31 32201 32 32200 33 32199 34 3...

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

3
4 5
3 4
2 3

output:

1
4 1 2 3 
1
3 1 2 
1
2 1 

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

3
2 3
3 5
4 6

output:

1
2 1 
1
3 1 2 
1
4 1 2 3 

result:

ok ok

Test #5:

score: 0
Accepted
time: 14ms
memory: 3624kb

input:

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

output:

1
5 1 4 2 3 
1
6 1 5 2 4 3 
1
2 7 1 6 3 5 4
1
8 1 7 2 6 3 4 5 
1
9 1 8 2 7 3 6 4 5 
1
10 1 9 2 8 3 5 6 4 7 
1
11 1 10 2 9 3 8 4 7 5 6 
1
12 1 11 2 10 3 8 5 7 6 4 9 
1
13 1 12 2 11 3 10 4 7 6 8 5 9 
1
14 1 13 2 12 3 11 4 10 5 9 6 8 7 
1
15 1 14 2 13 3 11 5 10 6 8 7 9 4 12 
1
16 1 15 2 14 3 13 4 11 6 ...

result:

ok ok

Test #6:

score: 0
Accepted
time: 10ms
memory: 3880kb

input:

410
444 475
285 366
386 437
242 311
716 799
803 894
436 443
313 344
190 279
649 672
143 180
968 1049
486 514
446 537
39 77
188 269
23 45
990 1052
709 727
985 1057
465 507
102 118
171 180
633 668
372 421
803 894
986 1027
525 535
499 510
611 661
342 346
958 1018
709 805
362 383
680 734
164 248
209 294...

output:

1
444 1 443 2 442 3 441 4 440 5 439 6 438 7 437 8 436 9 435 10 434 11 433 12 432 13 431 14 430 15 429 16 428 17 427 18 426 19 425 20 424 21 423 22 422 23 421 24 420 25 419 26 418 27 417 28 416 29 415 30 414 31 413 32 412 33 411 34 410 35 409 36 408 37 407 38 406 39 405 40 404 41 403 42 402 43 401 44...

result:

ok ok

Test #7:

score: 0
Accepted
time: 14ms
memory: 5728kb

input:

628
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
50 51
51 52
52 53
53 54
54 55
55 56...

output:

1
5 1 4 2 3 
1
6 1 5 2 4 3 
2
4 3 5 2 6 1 7
1
8 1 7 2 6 3 4 5 
1
9 1 8 2 7 3 6 4 5 
1
10 1 9 2 8 3 5 6 4 7 
1
11 1 10 2 9 3 8 4 7 5 6 
1
12 1 11 2 10 3 8 5 7 6 4 9 
1
13 1 12 2 11 3 10 4 7 6 8 5 9 
1
14 1 13 2 12 3 11 4 10 5 9 6 8 7 
1
15 1 14 2 13 3 11 5 10 6 8 7 9 4 12 
1
16 1 15 2 14 3 13 4 11 6 ...

result:

ok ok

Test #8:

score: 0
Accepted
time: 15ms
memory: 13352kb

input:

2
115943 115944
84057 84058

output:

1
115943 1 115942 2 115941 3 115940 4 115939 5 115938 6 115937 7 115936 8 115935 9 115934 10 115933 11 115932 12 115931 13 115930 14 115929 15 115928 16 115927 17 115926 18 115925 19 115924 20 115923 21 115922 22 115921 23 115920 24 115919 25 115918 26 115917 27 115916 28 115915 29 115914 30 115913 ...

result:

ok ok

Test #9:

score: 0
Accepted
time: 11ms
memory: 7016kb

input:

14
10433 10434
10387 10388
16756 16757
18905 18906
14013 14014
15198 15199
18709 18710
11750 11751
19145 19146
15134 15135
16029 16030
17126 17127
11802 11803
4613 4614

output:

1
10433 1 10432 2 10431 3 10430 4 10429 5 10428 6 10427 7 10426 8 10425 9 10424 10 10423 11 10422 12 10421 13 10420 14 10419 15 10418 16 10417 17 10416 18 10415 19 10414 20 10413 21 10412 22 10411 23 10410 24 10409 25 10408 26 10407 27 10406 28 10405 29 10404 30 10403 31 10402 32 10401 33 10400 34 1...

result:

ok ok

Test #10:

score: 0
Accepted
time: 12ms
memory: 6940kb

input:

10
20454 20455
20235 20236
20476 20477
20829 20830
20151 20152
20957 20958
20520 20521
20611 20612
20863 20864
14904 14905

output:

1
20454 1 20453 2 20452 3 20451 4 20450 5 20449 6 20448 7 20447 8 20446 9 20445 10 20444 11 20443 12 20442 13 20441 14 20440 15 20439 16 20438 17 20437 18 20436 19 20435 20 20434 21 20433 22 20432 23 20431 24 20430 25 20429 26 20428 27 20427 28 20426 29 20425 30 20424 31 20423 32 20422 33 20421 34 2...

result:

ok ok

Test #11:

score: 0
Accepted
time: 15ms
memory: 6936kb

input:

10
20000 20001
20001 20002
20002 20003
20003 20004
20004 20005
20005 20006
20006 20007
20007 20008
20008 20009
19964 19965

output:

1
20000 1 19999 2 19998 3 19997 4 19996 5 19995 6 19994 7 19993 8 19992 9 19991 10 19990 11 19989 12 19988 13 19987 14 19986 15 19985 16 19984 17 19983 18 19982 19 19981 20 19980 21 19979 22 19978 23 19977 24 19976 25 19975 26 19974 27 19973 28 19972 29 19971 30 19970 31 19969 32 19968 33 19967 34 1...

result:

ok ok

Test #12:

score: 0
Accepted
time: 15ms
memory: 5132kb

input:

10
20000 20004
20001 20006
20002 20005
20003 20005
20004 20007
20005 20010
20006 20010
20007 20012
20008 20009
19964 19967

output:

1
20000 1 19999 2 19998 3 19997 4 19996 5 19995 6 19994 7 19993 8 19992 9 19991 10 19990 11 19989 12 19988 13 19987 14 19986 15 19985 16 19984 17 19983 18 19982 19 19981 20 19980 21 19979 22 19978 23 19977 24 19976 25 19975 26 19974 27 19973 28 19972 29 19971 30 19970 31 19969 32 19968 33 19967 34 1...

result:

ok ok

Test #13:

score: 0
Accepted
time: 15ms
memory: 6900kb

input:

10
20000 34863
20001 40001
20002 26376
20003 33135
20004 39024
20005 31521
20006 28370
20007 24046
20008 40015
19964 39927

output:

1
20000 1 19999 2 19998 3 19997 4 19996 5 19995 6 19994 7 19993 8 19992 9 19991 10 19990 11 19989 12 19988 13 19987 14 19986 15 19985 16 19984 17 19983 18 19982 19 19981 20 19980 21 19979 22 19978 23 19977 24 19976 25 19975 26 19974 27 19973 28 19972 29 19971 30 19970 31 19969 32 19968 33 19967 34 1...

result:

ok ok

Test #14:

score: 0
Accepted
time: 15ms
memory: 6980kb

input:

10
20213 26231
20857 41713
20263 36372
20915 30059
20095 40189
20071 21843
20727 32658
20025 33443
20205 23840
16629 31941

output:

1
20213 1 20212 2 20211 3 20210 4 20209 5 20208 6 20207 7 20206 8 20205 9 20204 10 20203 11 20202 12 20201 13 20200 14 20199 15 20198 16 20197 17 20196 18 20195 19 20194 20 20193 21 20192 22 20191 23 20190 24 20189 25 20188 26 20187 27 20186 28 20185 29 20184 30 20183 31 20182 32 20181 33 20180 34 2...

result:

ok ok

Test #15:

score: 0
Accepted
time: 8ms
memory: 6184kb

input:

6
21212 23000
22326 40000
24445 24446
29692 30000
31290 32000
34275 60000

output:

1
21212 1 21211 2 21210 3 21209 4 21208 5 21207 6 21206 7 21205 8 21204 9 21203 10 21202 11 21201 12 21200 13 21199 14 21198 15 21197 16 21196 17 21195 18 21194 19 21193 20 21192 21 21191 22 21190 23 21189 24 21188 25 21187 26 21186 27 21185 28 21184 29 21183 30 21182 31 21181 32 21180 33 21179 34 2...

result:

ok ok

Test #16:

score: 0
Accepted
time: 14ms
memory: 5976kb

input:

240
819 1263
854 1328
855 895
861 1197
829 1169
828 907
838 899
813 1043
852 1082
813 1009
800 933
846 953
886 997
822 1285
788 1198
846 1014
878 972
803 1095
797 930
791 1277
827 1148
833 893
856 1183
857 1191
809 927
813 882
883 1175
816 1309
836 961
837 1260
843 1321
856 1060
827 1182
805 917
828...

output:

1
819 1 818 2 817 3 816 4 815 5 814 6 813 7 812 8 811 9 810 10 809 11 808 12 807 13 806 14 805 15 804 16 803 17 802 18 801 19 800 20 799 21 798 22 797 23 796 24 795 25 794 26 793 27 792 28 791 29 790 30 789 31 788 32 787 33 786 34 785 35 784 36 783 37 782 38 781 39 780 40 779 41 778 42 777 43 776 44...

result:

ok ok

Test #17:

score: 0
Accepted
time: 14ms
memory: 6568kb

input:

20
10000 11503
10000 12977
10000 10681
10000 10384
10000 10562
10000 11280
10000 12701
10000 11547
10000 10931
10000 10792
10000 13303
10000 10348
10000 12029
10000 11730
10000 12892
10000 12968
10000 12208
10000 12733
10000 13400
10000 12094

output:

1
10000 1 9999 2 9998 3 9997 4 9996 5 9995 6 9994 7 9993 8 9992 9 9991 10 9990 11 9989 12 9988 13 9987 14 9986 15 9985 16 9984 17 9983 18 9982 19 9981 20 9980 21 9979 22 9978 23 9977 24 9976 25 9975 26 9974 27 9973 28 9972 29 9971 30 9970 31 9969 32 9968 33 9967 34 9966 35 9965 36 9964 37 9963 38 99...

result:

ok ok

Test #18:

score: 0
Accepted
time: 14ms
memory: 6544kb

input:

41
5189 5719
7457 8200
6202 7454
23 45
6586 7820
4572 5263
3531 3790
7938 8977
9737 11008
1392 2693
1872 2273
8100 8359
1092 1514
4523 5259
5321 6693
6222 6289
1525 3049
689 1377
2171 3552
7124 7168
3065 4511
6523 7444
9903 10118
1179 1591
483 958
6243 7610
7535 7847
5418 6474
8243 9078
4268 4707
93...

output:

1
5189 1 5188 2 5187 3 5186 4 5185 5 5184 6 5183 7 5182 8 5181 9 5180 10 5179 11 5178 12 5177 13 5176 14 5175 15 5174 16 5173 17 5172 18 5171 19 5170 20 5169 21 5168 22 5167 23 5166 24 5165 25 5164 26 5163 27 5162 28 5161 29 5160 30 5159 31 5158 32 5157 33 5156 34 5155 35 5154 36 5153 37 5152 38 515...

result:

ok ok

Test #19:

score: 0
Accepted
time: 11ms
memory: 5948kb

input:

624
10 19
11 21
12 23
13 25
14 27
15 29
16 31
17 33
18 35
19 37
20 39
21 41
22 43
23 45
24 47
25 49
26 51
27 53
28 55
29 57
30 59
31 61
32 63
33 65
34 67
35 69
36 71
37 73
38 75
39 77
40 79
41 81
42 83
43 85
44 87
45 89
46 91
47 93
48 95
49 97
50 99
51 101
52 103
53 105
54 107
55 109
56 111
57 113
5...

output:

1
10 1 9 2 8 3 5 6 4 7 
1
11 1 10 2 9 3 8 4 7 5 6 
1
12 1 11 2 10 3 8 5 7 6 4 9 
1
13 1 12 2 11 3 10 4 7 6 8 5 9 
1
14 1 13 2 12 3 11 4 10 5 9 6 8 7 
1
15 1 14 2 13 3 11 5 10 6 8 7 9 4 12 
1
16 1 15 2 14 3 13 4 11 6 10 7 9 8 5 12 
1
17 1 16 2 15 3 14 4 11 7 10 8 9 6 12 5 13 
1
18 1 17 2 16 3 15 4 14...

result:

ok ok

Test #20:

score: 0
Accepted
time: 9ms
memory: 8604kb

input:

5
41135 41892
44605 45668
40361 40803
39058 40702
34841 36413

output:

1
41135 1 41134 2 41133 3 41132 4 41131 5 41130 6 41129 7 41128 8 41127 9 41126 10 41125 11 41124 12 41123 13 41122 14 41121 15 41120 16 41119 17 41118 18 41117 19 41116 20 41115 21 41114 22 41113 23 41112 24 41111 25 41110 26 41109 27 41108 28 41107 29 41106 30 41105 31 41104 32 41103 33 41102 34 4...

result:

ok ok

Test #21:

score: 0
Accepted
time: 10ms
memory: 11548kb

input:

3
89273 116963
83748 108080
26979 53957

output:

1
89273 1 89272 2 89271 3 89270 4 89269 5 89268 6 89267 7 89266 8 89265 9 89264 10 89263 11 89262 12 89261 13 89260 14 89259 15 89258 16 89257 17 89256 18 89255 19 89254 20 89253 21 89252 22 89251 23 89250 24 89249 25 89248 26 89247 27 89246 28 89245 29 89244 30 89243 31 89242 32 89241 33 89240 34 8...

result:

ok ok

Test #22:

score: 0
Accepted
time: 14ms
memory: 12264kb

input:

2
100000 100089
100000 100013

output:

1
100000 1 99999 2 99998 3 99997 4 99996 5 99995 6 99994 7 99993 8 99992 9 99991 10 99990 11 99989 12 99988 13 99987 14 99986 15 99985 16 99984 17 99983 18 99982 19 99981 20 99980 21 99979 22 99978 23 99977 24 99976 25 99975 26 99974 27 99973 28 99972 29 99971 30 99970 31 99969 32 99968 33 99967 34 ...

result:

ok ok

Test #23:

score: 0
Accepted
time: 3ms
memory: 7412kb

input:

1
27003 28000

output:

1
27003 1 27002 2 27001 3 27000 4 26999 5 26998 6 26997 7 26996 8 26995 9 26994 10 26993 11 26992 12 26991 13 26990 14 26989 15 26988 16 26987 17 26986 18 26985 19 26984 20 26983 21 26982 22 26981 23 26980 24 26979 25 26978 26 26977 27 26976 28 26975 29 26974 30 26973 31 26972 32 26971 33 26970 34 2...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1ms
memory: 5688kb

input:

3
6 10
7 8
2 3

output:

1
6 1 5 2 4 3 
2
4 3 5 2 6 1 7
1
2 1 

result:

ok ok

Test #25:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

30
2 3
3 4
3 5
4 5
4 6
4 7
5 6
5 7
5 8
5 9
6 7
6 8
6 9
6 10
6 11
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
8 14
8 15
9 10
9 11

output:

1
2 1 
1
3 1 2 
1
3 1 2 
1
4 1 2 3 
1
4 1 2 3 
1
4 1 2 3 
1
5 1 4 2 3 
1
5 1 4 2 3 
1
5 1 4 2 3 
1
5 1 4 2 3 
1
6 1 5 2 4 3 
1
6 1 5 2 4 3 
1
6 1 5 2 4 3 
1
6 1 5 2 4 3 
1
6 1 5 2 4 3 
2
4 3 5 2 6 1 7
1
2 7 1 6 3 5 4
1
2 7 1 6 3 5 4
1
2 7 1 6 3 5 4
1
2 7 1 6 3 5 4
1
2 7 1 6 3 5 4
1
8 1 7 2 6 3 4 5 
...

result:

ok ok