QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569400 | #9321. Permutations and Cycles (Minimum Version) | Crysfly | AC ✓ | 15ms | 13352kb | C++14 | 3.0kb | 2024-09-16 22:37:22 | 2024-09-16 22:37:24 |
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 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