fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.   Thuật toán:
  6.    - Phân tách 1..n thành blocks theo biểu diễn nhị phân của n (kích thước là powers of two).
  7.    - Với mỗi block (power of two) chạy "tournament internal" để làm tất cả phần tử trong block bằng sum(block).
  8.      (thực hiện các thao tác ghép cặp như mô tả).
  9.    - Giữ danh sách blocks (mỗi block lưu vector indices).
  10.    - Lặp: nếu có hai block cùng kích thước s, merge chúng bằng s thao tác op(A[k], B[k]).
  11.      Nếu không có, lấy block lớn nhất và split thành 2 block bằng nhau (chỉ chỉnh vector indices, không tốn op).
  12.    - Lặp tới khi chỉ còn 1 block (kích thước n).
  13.    - In các thao tác. Nếu số thao tác > 15*n thì in -1 (dự phòng).
  14. */
  15.  
  16. using vi = vector<int>;
  17. using pii = pair<int,int>;
  18.  
  19. vector<pii> ops;
  20.  
  21. // chạy tournament trên block có kích thước s = power of two
  22. // indices: vector<int> kích thước s; thực hiện ops ghi vào global ops
  23. void tournament_pow2(const vi &indices) {
  24.     int s = (int)indices.size();
  25.     // len = 1,2,4,... < s
  26.     for (int len = 1; len < s; len <<= 1) {
  27.         for (int start = 0; start < s; start += 2*len) {
  28.             for (int k = 0; k < len; ++k) {
  29.                 int u = indices[start + k];
  30.                 int v = indices[start + len + k];
  31.                 ops.emplace_back(u, v);
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. int main(){
  38.     ios::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.     int n;
  41.     if(!(cin >> n)) return 0;
  42.     vector<long long> a(n+1);
  43.     for(int i=1;i<=n;i++) cin >> a[i];
  44.  
  45.     // Step 1: partition 1..n into blocks of power-of-two sizes (by binary decomposition)
  46.     vector<vi> blocks; // each block is vector<int> indices
  47.     int cur = 1;
  48.     for (int b = 0; (1<<b) <= n; ++b) {
  49.         if ( (n >> b) & 1 ) {
  50.             int sz = (1<<b);
  51.             vi idx(sz);
  52.             for (int t = 0; t < sz; ++t) idx[t] = cur + t;
  53.             cur += sz;
  54.             blocks.push_back(idx);
  55.         }
  56.     }
  57.  
  58.     // Step 2: run tournament internal on each power-of-two block
  59.     for (auto &blk : blocks) {
  60.         tournament_pow2(blk);
  61.     }
  62.  
  63.     // Step 3: merge blocks by repeatedly pairing equal-size blocks; if none, split largest block
  64.     // We'll keep blocks in a multiset-like structure keyed by size; but we'll use vector and manual search
  65.     // because number of different blocks is <= number of bits (~15).
  66.     // For splitting, we just split indices vector into halves.
  67.     while ( (int)blocks.size() > 1 ) {
  68.         // try to find two blocks with same size
  69.         int m = blocks.size();
  70.         bool merged = false;
  71.         // map size -> index
  72.         unordered_map<int,int> mapSize;
  73.         mapSize.reserve(m*2);
  74.         for (int i = 0; i < m; ++i) {
  75.             int s = (int)blocks[i].size();
  76.             if (mapSize.find(s) == mapSize.end()) mapSize[s] = i;
  77.             else {
  78.                 int j = mapSize[s];
  79.                 if (j == i) continue;
  80.                 // merge blocks[j] and blocks[i]
  81.                 vi &A = blocks[j];
  82.                 vi &B = blocks[i];
  83.                 int ssz = s;
  84.                 // pairwise ops
  85.                 for (int k = 0; k < ssz; ++k) {
  86.                     ops.emplace_back(A[k], B[k]);
  87.                 }
  88.                 // create merged block (concatenate indices)
  89.                 vi M;
  90.                 M.reserve(ssz*2);
  91.                 for (int k = 0; k < ssz; ++k) M.push_back(A[k]);
  92.                 for (int k = 0; k < ssz; ++k) M.push_back(B[k]);
  93.  
  94.                 // replace blocks[j] by M, remove blocks[i]
  95.                 blocks[j] = move(M);
  96.                 // erase blocks[i]
  97.                 blocks.erase(blocks.begin() + i);
  98.                 merged = true;
  99.                 break;
  100.             }
  101.         }
  102.         if (!merged) {
  103.             // no two equal-size blocks -> split the largest block into two equal halves
  104.             int idxMax = 0;
  105.             int maxS = (int)blocks[0].size();
  106.             for (int i = 1; i < (int)blocks.size(); ++i) {
  107.                 if ((int)blocks[i].size() > maxS) {
  108.                     maxS = (int)blocks[i].size();
  109.                     idxMax = i;
  110.                 }
  111.             }
  112.             // split blocks[idxMax] into two halves
  113.             vi old = blocks[idxMax];
  114.             int half = maxS / 2;
  115.             vi A(old.begin(), old.begin() + half);
  116.             vi B(old.begin() + half, old.end());
  117.             blocks[idxMax] = move(A);
  118.             blocks.push_back(move(B));
  119.             // no operation added because splitting doesn't change values (elements equal inside block)
  120.         }
  121.  
  122.         // safety: if ops too many, break and print -1 later
  123.         if ((int)ops.size() > 15 * n) break;
  124.     }
  125.  
  126.     if ((int)ops.size() > 15 * n) {
  127.         cout << -1 << "\n";
  128.         return 0;
  129.     }
  130.  
  131.     // Optional: (sanity) we can assert blocks.size() == 1 and blocks[0].size() == n
  132.     // Print operations
  133.     cout << ops.size() << "\n";
  134.     for (auto &p : ops) {
  135.         cout << p.first << " " << p.second << "\n";
  136.     }
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3
1 2 3
stdout
copy 
-1
https://ideone.com/EYMlOW
language:
C++14 (gcc 8.3)
created:
13 days 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!