fork download
copy 
  1. /*
  2. // Sample code to perform I/O:
  3.  
  4. cin >> name;                            // Reading input from STDIN
  5. cout << "Hi, " << name << ".\n";        // Writing output to STDOUT
  6.  
  7. // Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
  8. */
  9.  
  10. // Write your code here
  11.     #include<iostream>
  12.     #include<algorithm>
  13.     #include<utility>
  14.     #include<vector>
  15.     #include <bits/stdc++.h>
  16.     using namespace std;
  17.  
  18.     int gcd(int a,int b)
  19.     {
  20.         if(a==0)
  21.             return b;
  22.         if(b==0)
  23.             return a;
  24.         if(a==b)
  25.             return a;
  26.         if(a>b)
  27.             return gcd(a-b,b);
  28.         else
  29.             return gcd(a,b-a);
  30.     }
  31.  
  32.     int main()
  33.     {
  34.       int t,n,m,l,r;
  35.       cin>>t;
  36.       while(t--)
  37.       {
  38.         cin>>n>>m;
  39.         vector<long int>a(n),b(n),c(n);
  40.         long int count=0;
  41.         vector<pair<int,int> > v;
  42.         for(int i=0;i<n;i++)
  43.         {
  44.             cin>>a[i];
  45.             b[i]=a[i];
  46.             c[i]=b[i];
  47.         }
  48.         for(int i=0;i<m;i++)
  49.         {
  50.           int u,V;
  51.           cin>>u>>V;
  52.           if(V>u)
  53.           v.push_back(make_pair(--V,--u));
  54.           else
  55.           v.push_back(make_pair(--u,--V));
  56.         }
  57.         for(auto it:v)
  58.         {
  59.           int l=it.first;r=it.second;
  60.           reverse(b.begin() + l, b.begin() + r);
  61.           // for(int j=l;j<=(l+r)/2;j++)
  62.           // {
  63.           //   swap(b[j],b[r-j]);
  64.           // }
  65.         }
  66.         // for(int i=0;i<n;i++)
  67.         //     cout<<a[i]<<" ";
  68.         sort(v.begin(),v.end());
  69.         // for(auto it:v)
  70.         //   cout<<it.first<<" "<<it.second<<endl;
  71.         do{
  72.           for(auto it:v)
  73.           {
  74.             int l=it.first;r=it.second;
  75.             reverse(a.begin() + l, a.begin() + r);
  76.             // for(int j=l;j<=(l+r)/2;j++)
  77.             // {
  78.             //   swap(a[j],a[r-j]);
  79.             // }
  80.           }
  81.         //   for(int i=0;i<n;i++)
  82.         //       cout<<a[i]<<" ";
  83.         //     cout<<endl;
  84.           for(int i=0;i<n;i++)
  85.           {
  86.             if(a[i]!=b[i])
  87.                break;
  88.             if(i==n-1)
  89.                count++;
  90.           }
  91.           for(int i=0;i<n;i++)
  92.             a[i]=c[i];
  93.         }while(next_permutation(v.begin(),v.end()));
  94.         int f=1;
  95.         for(int i=1;i<=m;i++)
  96.             f=f*i;
  97.         //cout<<count<<endl;
  98.  
  99.         cout<<count/gcd(count,f)<<"/"<<f/gcd(count,f)<<endl;
  100.       }
  101.       return 0;
  102.     }
  103.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
3 3
1 2 1
1 3
1 1
3 3
3 3
1 2 1
1 3
1 1
3 3
stdout
copy 
1/1
1/1
https://ideone.com/9srYgW
2
3 3
1 2 1
1 3
1 1
3 3
3 3
1 2 1
1 3
1 1
3 3
language:
C++14 (clang 8.0)
created:
5 years ago
visibility:
public

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!