fork download
copy 
  1. #define STRESS
  2. /**
  3.         *AUTHOR:Mayank Padia*
  4.         *Birla Institute of Technology,Mesra*
  5. **/
  6. #include<bits/stdc++.h>
  7. typedef long long ll;
  8. typedef double ld;
  9. #define vll vector<ll>
  10. #define vvll vector< vll >
  11. #define vld vector< ld >
  12. #define vvld vector< vld >
  13. #define pll pair<ll ,ll >
  14. #define vllp vector< pll >
  15. #define mp make_pair
  16. #define pb push_back
  17. #define MOD 1000000007
  18. #define endl "\n"
  19. #define test ll t;cin>>t;while(t--)
  20. #define all(v) v.begin(),v.end()
  21. #define rall(v) v.rbegin(),v.rend()
  22. #define F first
  23. #define S second
  24. #define MAX 1000000007
  25. #define cf_MOD 998244353
  26. #define forn(i,n) for(ll (i) = 0 ; (i) < (n) ; ++(i))
  27. #define for1(i,n) for(ll (i) = 1 ; (i) <= (n) ; ++(i))
  28. #define forr(i,n) for(ll (i) = (n)-1 ; (i)>=0 ; --(i))
  29. #define forab(i,a,b,c) for(ll (i) = a ; (i) <= (b) ; (i)+=(c))
  30. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  31. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  32. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  33. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  34. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  35. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  36.  
  37. using namespace std;
  38. #ifdef STRESS
  39. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  40. using rnd = uniform_int_distribution<int>;
  41. #endif
  42.  
  43. vll sieve;
  44. void Sieve(int N){
  45.     const ll maxn = N;
  46.     sieve.resize(maxn);
  47.     forn(i,maxn) sieve[i] = i;
  48.     sieve[1] = -1;
  49.     sieve[0] = -1;
  50.     forab(i,2,maxn,1) if(i == sieve[i]) for(ll j = 2*i ; j < maxn ; j+=i) if(sieve[j] == j) sieve[j] = i;
  51. }
  52. ll extended_GCD(ll a , ll b , ll &x , ll &y){
  53.     if(a == 0){
  54.         x = 0;
  55.         y = 1;
  56.         return b;
  57.     }
  58.     ll x1 , y1;
  59.     ll gcd = extended_GCD(b%a , a , x1 , y1);
  60.     x = y1 - (b/a)*x1;
  61.     y = x1;
  62.     return gcd;
  63. }
  64. ll power(ll a, ll b, ll m = MOD) {
  65.     a %= m;
  66.     ll res = 1;
  67.     while (b > 0) {
  68.         if (b & 1)
  69.             res = res * a % m;
  70.         a = a * a % m;
  71.         b >>= 1;
  72.     }
  73.     return res;
  74. }
  75. ll modinv(ll a , ll mod = MOD){
  76.     ll x , y;
  77.     extended_GCD(a , mod , x , y);
  78.     if(x < 0) x += mod;
  79.     return x;
  80. }
  81. //s=bitset<64>(val).to_string();
  82. ///////////////////////////////////////////////////////////////////////
  83. bool comp(pair<ll,ll> a, pair<ll,ll> b)
  84. {
  85.     if(a.S>b.S)
  86.         return true;
  87.     else if(a.S == b.S)
  88.     {
  89.         if(a.F<b.F)
  90.             return true;
  91.         return false;
  92.     }
  93.     else{
  94.         return false;
  95.     }
  96. }
  97. void solve(){
  98.     ll n;
  99.     //memset(a,-1,sizeof(a));
  100. #ifdef STRESS
  101.     n = 3;
  102. #else
  103.     cin>>n;
  104. #endif
  105.     ll a[n];
  106.     ll b[n];
  107.     for (int i = 0; i < n; ++i)
  108.     {
  109. #ifdef STRESS
  110.         a[i] = rnd(0, 10)(rng);
  111. #else
  112.         cin>>a[i];
  113. #endif
  114.         b[i] = a[i];
  115.     }
  116. #ifdef STRESS
  117.     vector<int> sta(a, a + n);
  118. #endif
  119.     sort(b,b+n);
  120.     vector<ll> v;
  121.     map<ll,vll> ma;
  122.     ll x = 0;
  123.     for (int i = 0; i < n; ++i)
  124.     {
  125.         for (int j = i+1; j < n; ++j)
  126.         {
  127.             if(i!=j)
  128.             {
  129.                 if(a[i]>a[j])
  130.                 {
  131.                     ma[j].pb(i);
  132.                     x++;
  133.                 }
  134.             }
  135.         }
  136.     }
  137.     vector<pair<ll,ll> > vp;
  138.     for(int i = n-1; i >= 0; --i)
  139.     {
  140.         if(ma[i].size() == 0)
  141.             continue;
  142.         ll in = -1;
  143.         for (int j = 0; j < ma[i].size(); ++j)
  144.         {
  145.             if(a[ma[i][j]] == b[i])
  146.             {
  147.                 in = j;
  148.                 break;
  149.             }
  150.         }
  151.         ll ff = 0;
  152.         for (int j = 0; j < ma[i].size(); ++j)
  153.         {
  154.             if(ma[i][j] != in)
  155.             {
  156.                 vp.pb({ma[i][j] + 1,i+1});
  157.                 swap(a[i], a[ma[i][j]]);
  158.             }
  159.             else{
  160.                 ff = 1;
  161.             }
  162.         }
  163.         if(ff == 1){
  164.         vp.pb({in + 1, i + 1});
  165.         if(vp.size()>x)
  166.         {
  167.             cout<<"Exceeded at "<<i<<" "<<ma[i].size()<<endl;
  168.             return;
  169.         }
  170.         swap(a[i], a[in]);
  171.         }
  172.     }
  173. #ifndef STRESS
  174.     cout<<vp.size()<<endl;
  175.     for (int i = 0; i < vp.size(); ++i)
  176.     {
  177.         cout<<vp[i].F<<" "<<vp[i].S<<endl;
  178.     }
  179. #endif
  180. #ifdef STRESS
  181.     auto temp = sta;
  182.     for (auto p: vp)
  183.         swap(temp[p.first - 1], temp[p.second - 1]);
  184.     if (is_sorted(temp.begin(), temp.end()))
  185.         cout << "OK" << endl;
  186.     else {
  187.         cout << sta.size() << '\n';
  188.         for (int i: sta)
  189.             cout << i << ' ';
  190.         cout << endl;
  191.     }
  192. #else
  193.     cout<<vp.size()<<endl;
  194.     for (int i = 0; i < vp.size(); ++i)
  195.     {
  196.         cout<<vp[i].F<<" "<<vp[i].S<<endl;
  197.     }
  198. #endif
  199.     }
  200.  
  201. int main(){
  202. #ifndef STRESS
  203.         #ifndef ONLINE_JUDGE
  204.             freopen("input.txt","r",stdin);
  205.             freopen("output.txt","w",stdout);
  206.         #endif
  207. #endif
  208.     ios::sync_with_stdio(0); cin.tie(0);
  209.     int t=1;
  210.     //cin>>t;
  211. #ifdef STRESS
  212.     cin >> t;
  213. #endif
  214.     while(t--){
  215.         solve();
  216.     }
  217.     #ifndef ONLINE_JUDGE
  218.         cout<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
  219.     #endif
  220. return 0;
  221. }
  222.  
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
30
stdout
copy 
OK
3
10 10 0 
OK
OK
OK
OK
OK
3
4 4 0 
OK
OK
OK
OK
OK
OK
3
8 8 1 
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
https://ideone.com/fRaNLH
language:
C++ (gcc 8.3)
created:
4 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!