fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define ff first
  8. #define ss second
  9. #define pii pair<int,int>
  10. #define pll pair<long long, long long>
  11. #define vi vector<int>
  12. #define vl vector<long long>
  13. #define pb push_back
  14. #define rep(i, b) for(int i = 0; i < (b); ++i)
  15. #define rep2(i,a,b) for(int i = a; i <= (b); ++i)
  16. #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
  17. #define count_bits(x) __builtin_popcountll((x))
  18. #define all(x) (x).begin(),(x).end()
  19. #define siz(x) (int)(x).size()
  20. #define forall(it,x) for(auto& it:(x))
  21. using namespace __gnu_pbds;
  22. using namespace std;
  23. typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  24. //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
  25. //ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
  26. const int INF = 1e9+50;
  27. const ll INF_L = 1e18+40;
  28. const ll MOD = 1e9+7;
  29.  
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  33.     //random_start();
  34.     int n,t;
  35.     cin >> n >> t;
  36.     vi arr(n+1);
  37.     vi arr2(n+1);
  38.     rep(i,n) cin >> arr[i+1];
  39.     rep2(i,1,n) arr2[i] = arr[i];
  40.     vector<pii> ans;
  41.     if(t == 1)
  42.     {
  43.         vector<pii> sort_arr;
  44.         rep(i,n) sort_arr.pb({-arr[i+1],i+1});
  45.         sort(all(sort_arr));
  46.         rep(i,n)
  47.         {
  48.             rep2(j,1,n-1-i)
  49.             {
  50.                 ans.pb({j,j+1});
  51.                 arr[j] ^= arr[j+1];
  52.             }
  53.             pii m = {-1,-1};
  54.             rep2(j,1,n-i)
  55.             {
  56.                 m = max(m,{arr2[j],j});
  57.             }
  58.             int x = m.ss;
  59.           //  cout << x << " x\n";
  60.           //  rep2(k,1,n) cout << arr[k] << " ";
  61.            // cout << " arr\n";
  62.             rep2(j,x,n-1-i)
  63.             {
  64.                 ans.pb({j+1,j});
  65.                 arr[j+1] ^= arr[j];
  66.             }
  67.             for(int j = x-2; j >= 1; j--)
  68.             {
  69.                 ans.pb({j,j+1});
  70.                 arr[j] ^= arr[j+1];
  71.             }
  72.             rep2(i,x,n-1)
  73.             {
  74.                 arr2[i] = arr2[i+1];
  75.             }
  76.           //  rep2(k,1,n) cout << arr[k] << " ";
  77.           //  cout << " arr\n";
  78.          //   cout << "\n";
  79.         }
  80.         for(int i = n-1; i >= 1; i--)
  81.         {
  82.             ans.pb({i,i+1});
  83.             arr[i] ^= arr[i+1];
  84.         }
  85.        // rep2(k,1,n) cout << arr[k] << " ";
  86.        // cout << " arr\n";
  87.     }
  88.     if(t == 2)
  89.     {
  90.         int cur_suf = n;
  91.         for(int bit = 19; bit >= 0; bit--)
  92.         {
  93.             bool was = false;
  94.             rep2(i,1,cur_suf)
  95.             {
  96.                 if(arr[i] & (1 << bit))
  97.                 {
  98.                     was = true;
  99.                     int cur = i-1;
  100.                     while(cur >= 1 && (arr[cur] & (1 << bit)) == 0)
  101.                     {
  102.                         ans.pb({cur,cur+1});
  103.                         arr[cur] ^= arr[cur+1];
  104.                         cur--;
  105.                     }
  106.                     cur = i+1;
  107.                     while(cur <= cur_suf && (arr[cur] & (1 << bit)) == 0)
  108.                     {
  109.                         ans.pb({cur,cur-1});
  110.                         arr[cur] ^= arr[cur-1];
  111.                         cur++;
  112.                     }
  113.                 }
  114.             }
  115.             if(was == true)
  116.             {
  117.                 rep2(i,2,cur_suf)
  118.                 {
  119.                     ans.pb({i-1,i});
  120.                     arr[i-1] ^= arr[i];
  121.                 }
  122.                 cur_suf--;
  123.             }
  124.           //  rep2(i,1,n) cout << arr[i] << " ";
  125.            // cout << " arr\n";
  126.         }
  127.     }
  128.     cout << siz(ans) << "\n";
  129.     forall(it,ans) cout << it.ff << " " << it.ss << "\n";
  130. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
4 1 
2 1 3 7
stdout
copy 
13
1 2
2 3
3 4
2 3
1 2
1 2
2 3
1 2
1 2
2 1
3 4
2 3
1 2
https://ideone.com/5S6e8H
language:
C++14 (gcc 8.3)
created:
15 hours 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!