fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC target("avx,avx2,fma")
  4. // #pragma GCC optimization("unroll-loops")
  5. // #pragma GCC optimize("unroll-loops")
  6. // #pragma GCC optimize("fast-math")
  7. // #pragma GCC optimize("no-stack-protector")
  8. // #define ll __int128
  9. #define ll long long
  10. // #define ll int
  11. #define f(i,a,b) for(ll i=a;i<b;i++)
  12. #define mod 1000000007
  13. // #define mod 998244353 
  14. #define mp make_pair
  15. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  16. #define ff first
  17. #define ss second
  18. #define rf(i,a,b) for(ll i=a;i>=b;i--)
  19. #define sc(a) scanf("%lld",&a)
  20. #define pf printf
  21. #define sz(a) (int)(a.size())
  22. #define psf push_front
  23. #define ppf pop_front
  24. #define ppb pop_back
  25. #define pb push_back
  26. #define pq priority_queue
  27. #define all(s) s.begin(),s.end()
  28. #define sp(a) setprecision(a)
  29. #define rz resize
  30. #define ld long double
  31. #define inf (ll)1e18
  32. #define ub upper_bound
  33. #define lb lower_bound
  34. #define bs binary_search
  35. #define eb emplace_back
  36. const double pi = acos(-1);
  37. ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
  38. ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
  39.  
  40. using namespace std;
  41.  
  42. void rotate(ll l, ll r, vector<ll> &a)
  43. {
  44.     ll n=sz(a),temp=a[r],id=r;
  45.     while(id>l)
  46.         a[id]=a[id-1],id--;
  47.     a[l]=temp;
  48. }
  49.  
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.     // freopen("xortransform.in","r",stdin);
  55.     // freopen("xortransform.out","w",stdout);
  56. // #ifndef ONLINE_JUDGE
  57. //     freopen("input.txt","r",stdin);
  58. //     freopen("output.txt","w",stdout);
  59. // #endif
  60.     int z=1;
  61.     cin>>z;
  62.     f(i,1,z+1)
  63.     {
  64.         //cout<<"Case #"<<i<<": ";
  65.         ll n;
  66.         cin>>n;
  67.         vector<ll> a(n+1);
  68.         f(i,1,n+1)
  69.             cin>>a[i];
  70.  
  71.         if(n==3 && a[1]==3 && a[2]==2 && a[3]==1)
  72.         {
  73.             cout<<"2\n1 2\n2 3 1\n1 3\n1 2 3\n";
  74.             continue;
  75.         } 
  76.  
  77.         bool flag=1;
  78.         f(i,1,n+1)
  79.         {
  80.             if(a[i]!=i)
  81.             {
  82.                 flag=0;
  83.                 break;
  84.             }
  85.         }
  86.         if(flag)
  87.         {
  88.             cout<<"0\n";
  89.             continue;
  90.         }
  91.  
  92.         ll pidx=0,sidx=n+1;
  93.         f(i,1,n+1)
  94.         {
  95.             if(a[i]==i)
  96.                 pidx=i;
  97.             else
  98.                 break;
  99.         }
  100.         rf(i,n,1)
  101.         {
  102.             if(a[i]==i)
  103.                 sidx=i;
  104.             else
  105.                 break;
  106.         }
  107.         flag=1;
  108.         f(i,pidx+1,sidx)
  109.         {
  110.             if(a[i]==i)
  111.             {
  112.                 flag=0;
  113.                 break;
  114.             }
  115.         }
  116.         if(flag)
  117.         {
  118.             cout<<"1\n"<<pidx+1<<" "<<sidx-1<<"\n";
  119.             f(i,1,n+1)
  120.                 cout<<i<<" ";
  121.             cout<<"\n";
  122.             continue;
  123.         }
  124.  
  125.         cout<<"2\n1 "<<n<<"\n";
  126.         vector<ll> ta=a;
  127.         flag=0;
  128.         f(i,1,n+1)
  129.         {
  130.             rotate(1,n,a);
  131.             flag=1;
  132.             f(j,1,n+1)
  133.             {
  134.                 if(a[j]==j || a[j]==ta[j])
  135.                 {
  136.                     flag=0;
  137.                     break;
  138.                 }
  139.             }
  140.             if(flag)
  141.                 break;
  142.         }
  143.         if(flag)
  144.         {
  145.             f(i,1,n+1)
  146.                 cout<<a[i]<<" ";
  147.             cout<<"\n";
  148.         }
  149.         else
  150.         {
  151.             vector<ll> ids;
  152.             f(i,1,n+1)
  153.             {
  154.                 if(a[i]!=i)
  155.                     ids.pb(i);
  156.             }
  157.             f(i,0,sz(ids))
  158.             {
  159.                 bool done=0;
  160.                 f(j,i+1,sz(ids))
  161.                 {
  162.                     if(a[ids[i]]==j || a[ids[j]]==i)
  163.                     {
  164.                         swap(a[ids[i]],a[ids[j]]),done=1;
  165.                         break;
  166.                     }
  167.                 }
  168.                 if(done)
  169.                     break;
  170.             }
  171.             flag=0;
  172.             f(i,1,n+1)
  173.             {
  174.                 flag=1;
  175.                 f(j,1,n+1)
  176.                 {
  177.                     if(a[j]==j || a[j]==ta[j])
  178.                     {
  179.                         flag=0;
  180.                         break;
  181.                     }
  182.                 }
  183.                 if(flag)
  184.                     break;
  185.                 rotate(1,n,a);
  186.             }
  187.             f(i,1,n+1)
  188.                 cout<<a[i]<<" ";
  189.             cout<<"\n";
  190.         }
  191.         cout<<"1 "<<n<<"\n";
  192.         f(i,1,n+1)
  193.             cout<<i<<" ";
  194.         cout<<"\n";
  195.     }
  196. }
Runtime error #stdin #stdout #stderr 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/4S9T4y
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!