#include <bits/stdc++.h> using namespace std; int T[3100]; int T2[3100]; int Poz[3100]; int Wyk[3100]; int P[3100]; vector<vector<int> > O1; vector<vector<int> > O2; void zm(int a,int b){ Poz[T[a]]=b; Poz[T[b]]=a; swap(T[a],T[b]); return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>T[i]; T2[i]=T[i]; Poz[T[i]]=i; } sort(T2+1,T2+n+1); vector<int> W; vector<int> W2; bool kon=true; while(1==1){ W.clear(); W2.clear(); kon=true; for(int i=1;i<=n;i++){ Wyk[i]=0; if(T[i]==T2[i]){ P[i]=-1; continue; } kon=false; P[i]=Poz[T2[i]]; } if(kon==true){ break; } for(int i=1;i<=n;i++){ //cout<<"y"<<i<<"\n"; if(P[i]==-1){ continue; } int ii=i; if(Wyk[ii]==1){ continue; } // cout<<"st"<<ii<<" "<<P[ii]<<"\n"; while(P[ii]!=-1 and Wyk[P[ii]]==0){ //cout<<ii<<" "<<P[ii]<<"\n"; if(Wyk[ii]==0){ W.push_back(ii); W2.push_back(P[ii]); Wyk[ii]=1; Wyk[P[ii]]=1; zm(ii,P[ii]); } ii=P[ii]; } } O1.push_back(W); O2.push_back(W2); // for(int i=1;i<=n;i++){ // cout<<T[i]<<" "; //} //cout<<"\n"; } cout<<O1.size()<<"\n"; for(int j=0;j<O1.size();j++){ cout<<O1[j].size()*2<<"\n"; for(int i=0;i<O1[j].size();i++){ cout<<O1[j][i]<<" "; } for(int i=O2[j].size()-1;i>=0;i--){ cout<<O2[j][i]<<" "; } cout<<"\n"; } }
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 | #include <bits/stdc++.h> using namespace std; int T[3100]; int T2[3100]; int Poz[3100]; int Wyk[3100]; int P[3100]; vector<vector<int> > O1; vector<vector<int> > O2; void zm(int a,int b){ Poz[T[a]]=b; Poz[T[b]]=a; swap(T[a],T[b]); return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>T[i]; T2[i]=T[i]; Poz[T[i]]=i; } sort(T2+1,T2+n+1); vector<int> W; vector<int> W2; bool kon=true; while(1==1){ W.clear(); W2.clear(); kon=true; for(int i=1;i<=n;i++){ Wyk[i]=0; if(T[i]==T2[i]){ P[i]=-1; continue; } kon=false; P[i]=Poz[T2[i]]; } if(kon==true){ break; } for(int i=1;i<=n;i++){ //cout<<"y"<<i<<"\n"; if(P[i]==-1){ continue; } int ii=i; if(Wyk[ii]==1){ continue; } // cout<<"st"<<ii<<" "<<P[ii]<<"\n"; while(P[ii]!=-1 and Wyk[P[ii]]==0){ //cout<<ii<<" "<<P[ii]<<"\n"; if(Wyk[ii]==0){ W.push_back(ii); W2.push_back(P[ii]); Wyk[ii]=1; Wyk[P[ii]]=1; zm(ii,P[ii]); } ii=P[ii]; } } O1.push_back(W); O2.push_back(W2); // for(int i=1;i<=n;i++){ // cout<<T[i]<<" "; //} //cout<<"\n"; } cout<<O1.size()<<"\n"; for(int j=0;j<O1.size();j++){ cout<<O1[j].size()*2<<"\n"; for(int i=0;i<O1[j].size();i++){ cout<<O1[j][i]<<" "; } for(int i=O2[j].size()-1;i>=0;i--){ cout<<O2[j][i]<<" "; } cout<<"\n"; } } |