niyaznigmatullin

Untitled

Feb 15th, 2016
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 2016;
  6. const int A = 63;
  7. const int B = 32;
  8.  
  9. int a[7777];
  10.  
  11. int pr[144][144][144];
  12.  
  13. vector <int> get_heap(vector <int> idx, int md) {
  14.   int n = idx.size();
  15.   assert(n == 2 * md - 1);
  16.   for (int i = 0; i <= n; i++) {
  17.     for (int j = 0; j <= md; j++) {
  18.       for (int rm = 0; rm < md; rm++) {
  19.         pr[i][j][rm] = -1;
  20.       }
  21.     }
  22.   }
  23.   pr[0][0][0] = 0;
  24.   for (int i = 0; i < n; i++) {
  25.     for (int j = 0; j <= md; j++) {
  26.       for (int rm = 0; rm < md; rm++) {
  27.         if (pr[i][j][rm] == -1) {
  28.           continue;
  29.         }
  30.         if (pr[i + 1][j][rm] == -1) {
  31.           pr[i + 1][j][rm] = 0;
  32.         }
  33.         if (j < md) {
  34.           int nrm = (rm + a[idx[i]]) % md;
  35.           if (pr[i + 1][j + 1][nrm] == -1) {
  36.             pr[i + 1][j + 1][nrm] = 1;
  37.           }
  38.         }
  39.       }
  40.     }
  41.   }
  42.   assert(pr[n][md][0] != -1);
  43.   vector <int> ret;
  44.   int j = md, rm = 0;
  45.   for (int i = n; i > 0; i--) {
  46.     if (pr[i][j][rm] == 1) {
  47.       ret.push_back(idx[i - 1]);
  48.       j--;
  49.       rm = ((rm - a[idx[i - 1]]) % md + md) % md;
  50.     }
  51.   }
  52.   assert(ret.size() == md);
  53.   return ret;
  54. }
  55.  
  56. vector <int> heap[7777];
  57.  
  58. int main() {
  59.   int cnt = 6666;
  60.   vector <int> idx(cnt);
  61.   for (int i = 0; i < cnt; i++) {
  62.     scanf("%d", &a[i]);
  63.     idx[i] = i;
  64.   }
  65.   for (int id = 0; id < 2 * B - 1; id++) {
  66.     vector <int> b;
  67.     for (int i = 0; i < 2 * A - 1; i++) {
  68.       b.push_back(idx.back());
  69.       idx.pop_back();
  70.     }
  71.     heap[id] = get_heap(b, A);
  72.     for (int i = 0; i < (int) b.size(); i++) {
  73.       bool used = false;
  74.       for (int j = 0; j < (int) heap[id].size(); j++) {
  75.         if (b[i] == heap[id][j]) {
  76.           used = true;
  77.           break;
  78.         }
  79.       }
  80.       if (!used) {
  81.         idx.push_back(b[i]);
  82.       }
  83.     }
  84.   }
  85.   for (int id = 0; id < 2 * B - 1; id++) {
  86.     int sum = 0;
  87.     for (int j = 0; j < (int) heap[id].size(); j++) {
  88.       sum += a[heap[id][j]];
  89.     }
  90.     a[cnt + id] = sum;
  91.   }
  92.   vector <int> fake;
  93.   for (int id = 0; id < 2 * B - 1; id++) {
  94.     fake.push_back(cnt + id);
  95.   }
  96.   vector <int> heaps = get_heap(fake, B);
  97.   vector <int> res;
  98.   for (int i = 0; i < (int) heaps.size(); i++) {
  99.     for (int j = 0; j < (int) heap[heaps[i] - cnt].size(); j++) {
  100.       res.push_back(heap[heaps[i] - cnt][j]);
  101.     }
  102.   }
  103.   sort(res.begin(), res.end());
  104.   int total = 0;
  105.   for (int i = 0; i < (int) res.size(); i++) {
  106.     total += a[res[i]];
  107.   }
  108.   assert(total % N == 0);
  109.   for (int i = 0; i < (int) res.size(); i++) {
  110.     printf("%d\n", res[i] + 1);
  111.   }
  112.   return 0;
  113. }
Add Comment
Please, Sign In to add comment