QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569409 | #9332. Permutations and Cycles (Maximum Version) | Crysfly | AC ✓ | 13ms | 8616kb | C++14 | 3.6kb | 2024-09-16 22:38:37 | 2024-09-16 22:38:37 |
Judging History
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