QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569409#9332. Permutations and Cycles (Maximum Version)CrysflyAC ✓13ms8616kbC++143.6kb2024-09-16 22:38:372024-09-16 22:38:37

Judging History

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

  • [2024-09-16 22:38:37]
  • 评测
  • 测评结果:AC
  • 用时:13ms
  • 内存:8616kb
  • [2024-09-16 22:38:37]
  • 提交

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 int long long
#define ull unsigned 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;
}

int mod=1000000007;
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#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 2000005
#define inf 0x3f3f3f3f

int n,p[maxn],k;

int q[maxn];
int vis[maxn];
int calc(){
	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;
}

void brute()
{
	For(i,1,n)p[i]=i;
	auto chk = [&](){
		For(i,1,n-1) if(p[i]+p[i+1]>k) return 0;
		return 1;
	};
	int mx=0;
	do{
		if(chk()){
			int res=calc();
			if(res>mx){
				mx=res;
				For(i,1,n)q[i]=p[i];
			}
		}
	}while(next_permutation(p+1,p+n+1));
	cout<<mx<<"\n";
	For(i,1,n)cout<<q[i]<<" ";cout<<"\n";
}

bool chk(int pos){
	auto chk_k = [&](){
		For(i,1,n-1) if(p[i]+p[i+1]>k) return 0;
		return 1;
	};
	if(n-pos<=2){
		For(i,1,n) p[i]=i;
		return chk_k();
	}
	For(i,1,pos)p[i]=i;
	p[n-1]=pos+1; p[n]=n;
	int l=pos+2,r=n-1,u=pos+1,op=1,pl=pos+1,pr=n-2;
	while(pl<=pr){
		if(pl==pr){
			p[pl]=l;
			break;
		}
		if(op)p[pl]=r--,p[pr]=r--;
		else p[pl]=l++,p[pr]=l++;
		op^=1,++pl,--pr;
	}
	//For(i,1,n)cout<<p[i]<<" ";cout<<"\n";
	return chk_k();
}

void work()
{
	n=read(),k=read();
	if(n<=3) {
		brute();
		return;
	}
	int l=0,r=n,pos=0;
	assert(chk(0));
	while(l<=r){
		int mid=l+r>>1;
		if(chk(mid))pos=mid,l=mid+1;
		else r=mid-1;
	}
	assert(chk(pos));
	cout<<calc()<<"\n";
	For(i,1,n)cout<<p[i]<<' ';cout<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7756kb

input:

3
2 3
3 4
3 5

output:

2
1 2 
2
2 1 3 
3
1 2 3 

result:

ok ok

Test #2:

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

input:

16
5 8
4 5
2 3
7 12
5 8
10 15
7 10
10 14
5 9
2 3
10 17
8 11
8 14
3 4
9 16
5 8

output:

4
1 2 4 3 5 
3
3 2 1 4 
2
1 2 
6
1 2 3 4 6 5 7 
4
1 2 4 3 5 
9
1 2 3 4 9 6 7 8 5 10 
6
1 2 6 4 5 3 7 
8
1 2 3 9 5 7 6 8 4 10 
5
1 2 3 4 5 
2
1 2 
9
1 2 3 4 5 6 9 8 7 10 
7
1 2 7 4 5 6 3 8 
7
1 2 3 4 5 7 6 8 
2
2 1 3 
8
1 2 3 4 5 6 8 7 9 
4
1 2 4 3 5 

result:

ok ok

Test #3:

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

input:

22
539 540
9618 19087
8415 9369
236 471
2103 3286
6124 6125
3792 7583
2164 4327
1012 1013
2916 2917
3609 4447
6177 6178
4550 4953
3477 6953
2467 4933
9318 16901
5467 8084
3516 6584
2128 2129
6427 9233
7272 11558
8673 11944

output:

404
538 2 536 4 534 6 532 8 530 10 528 12 526 14 524 16 522 18 520 20 518 22 516 24 514 26 512 28 510 30 508 32 506 34 504 36 502 38 500 40 498 42 496 44 494 46 492 48 490 50 488 52 486 54 484 56 482 58 480 60 478 62 476 64 474 66 472 68 470 70 468 72 466 74 464 76 462 78 460 80 458 82 456 84 454 86...

result:

ok ok

Test #4:

score: 0
Accepted
time: 6ms
memory: 5724kb

input:

359
100 101
101 201
102 103
103 205
104 207
105 106
106 107
107 108
108 109
109 110
110 111
111 221
112 113
113 114
114 115
115 116
116 117
117 118
118 235
119 120
120 121
121 122
122 123
123 124
124 125
125 249
126 251
127 128
128 255
129 257
130 131
131 132
132 133
133 134
134 267
135 269
136 137
...

output:

75
99 2 97 4 95 6 93 8 91 10 89 12 87 14 85 16 83 18 81 20 79 22 77 24 75 26 73 28 71 30 69 32 67 34 65 36 63 38 61 40 59 42 57 44 55 46 53 48 51 50 49 52 47 54 45 56 43 58 41 60 39 62 37 64 35 66 33 68 31 70 29 72 27 74 25 76 23 78 21 80 19 82 17 84 15 86 13 88 11 90 9 92 7 94 5 96 3 98 1 100 
101
...

result:

ok ok

Test #5:

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

input:

38
5693 10440
5550 6937
5036 7510
5826 7748
4790 4947
5432 9412
5269 10320
5561 8957
5776 7407
5044 9330
5764 7194
5988 8034
5095 5877
5360 5944
5560 10514
5869 7762
5187 7513
5457 8552
5103 7318
5238 7068
5903 11784
5887 8297
5107 6734
5211 5650
5410 6562
5562 8119
4976 6122
5071 8842
5225 8451
498...

output:

5456
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok ok

Test #6:

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

input:

1
200000 364465

output:

191116
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #7:

score: 0
Accepted
time: 13ms
memory: 6488kb

input:

1
200000 399999

output:

200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #8:

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

input:

13
17766 31770
18662 18663
13358 13370
19528 25756
14119 21269
13110 26219
17381 31063
12457 12458
17028 24550
16194 27456
12720 12879
10558 10559
17119 17120

output:

16825
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok ok

Test #9:

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

input:

15
15374 16312
14411 28195
12508 24643
10483 20124
15267 15606
15272 30542
17551 35031
15661 30951
11970 12684
16166 16745
13873 27274
12511 24167
11005 21639
12782 13375
5166 5174

output:

11765
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok ok

Test #10:

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

input:

2
100000 100001
100000 199999

output:

75000
99999 2 99997 4 99995 6 99993 8 99991 10 99989 12 99987 14 99985 16 99983 18 99981 20 99979 22 99977 24 99975 26 99973 28 99971 30 99969 32 99967 34 99965 36 99963 38 99961 40 99959 42 99957 44 99955 46 99953 48 99951 50 99949 52 99947 54 99945 56 99943 58 99941 60 99939 62 99937 64 99935 66 9...

result:

ok ok

Test #11:

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

input:

4
50000 75000
50000 52232
50000 99332
50000 93827

output:

43750
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok ok

Test #12:

score: 0
Accepted
time: 7ms
memory: 5796kb

input:

135
1601 1829
1944 3450
2000 3917
1261 1689
1404 1832
1158 1511
1990 3640
1323 2459
1420 1826
1639 1748
1309 2246
1043 1215
1069 2094
1577 2985
1239 2343
1066 1718
1106 1512
1122 1444
1375 1620
1452 2833
1844 3508
1841 2159
1127 1330
1894 1999
1896 2142
1008 1393
1794 3498
1042 1371
1960 2126
1559 2...

output:

1258
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok ok

Test #13:

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

input:

14
18303 18463
10001 10139
12939 13145
13431 26772
14731 29091
19418 38625
18746 37401
10807 21403
15272 30510
15489 15543
18814 37480
13039 13190
13460 13799
5550 10822

output:

13767
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok ok

Test #14:

score: 0
Accepted
time: 13ms
memory: 8272kb

input:

1
200000 390071

output:

197518
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #15:

score: 0
Accepted
time: 13ms
memory: 6504kb

input:

1
200000 390000

output:

197500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #16:

score: 0
Accepted
time: 13ms
memory: 6496kb

input:

1
200000 299999

output:

175000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #17:

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

input:

1
200000 300000

output:

175000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #18:

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

input:

1
200000 219292

output:

154823
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #19:

score: 0
Accepted
time: 13ms
memory: 8540kb

input:

1
200000 398485

output:

199621
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #20:

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

input:

1
200000 200011

output:

150003
1 2 3 4 5 6 7 8 9 10 199999 12 199997 14 199995 16 199993 18 199991 20 199989 22 199987 24 199985 26 199983 28 199981 30 199979 32 199977 34 199975 36 199973 38 199971 40 199969 42 199967 44 199965 46 199963 48 199961 50 199959 52 199957 54 199955 56 199953 58 199951 60 199949 62 199947 64 19...

result:

ok ok

Test #21:

score: 0
Accepted
time: 13ms
memory: 6484kb

input:

1
200000 364469

output:

191117
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #22:

score: 0
Accepted
time: 13ms
memory: 8596kb

input:

1
200000 200002

output:

150000
1 199999 3 199997 5 199995 7 199993 9 199991 11 199989 13 199987 15 199985 17 199983 19 199981 21 199979 23 199977 25 199975 27 199973 29 199971 31 199969 33 199967 35 199965 37 199963 39 199961 41 199959 43 199957 45 199955 47 199953 49 199951 51 199949 53 199947 55 199945 57 199943 59 19994...

result:

ok ok

Test #23:

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

input:

1
200000 386869

output:

196717
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #24:

score: 0
Accepted
time: 13ms
memory: 8476kb

input:

1
200000 398856

output:

199714
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok ok

Test #25:

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

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:

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

result:

ok ok