Guest User

Untitled

a guest
Feb 14th, 2016
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <queue>
  8. #include <list>
  9. #include <map>
  10. #include <set>
  11. #include <stdlib.h>
  12. #include <sstream>
  13. #include <assert.h>
  14. #include <memory.h>
  15. #include <string.h>
  16. #include <time.h>
  17.  
  18. using namespace std;
  19.  
  20. #pragma comment(linker, "/STACK:100000000")
  21.  
  22. #define mp make_pair
  23. #define pb push_back
  24. #define ll long long
  25. #define ull long long
  26. #define sz(x) (int)(x).size()
  27. #define fr(i,a,b) for(int i = (a);i <= (b);i++)
  28. #define fd(i,a,b) for(int i = (a);i >= (b);i--)
  29.  
  30. int ri(){int x;scanf("%d",&x);return x;}
  31.  
  32. pair<int, int> mas[7777];
  33.  
  34. int cnt = 0;
  35. vector<int> idx2016;
  36.  
  37. int n = 6666;
  38.  
  39. bool my_shuffle() {
  40.     random_shuffle(mas, mas + n);
  41.     int ost = 0;
  42.     for(int i = 0; i < 2016; i++) {
  43.         if(ost == 0 && i + cnt > 2015) {
  44.             vector<int> v;
  45.             for(int j = 0; j < i; j++) v.pb(mas[j].second);
  46.             while(sz(v) < 2016) {
  47.                 v.pb(idx2016.back());
  48.                 idx2016.pop_back();
  49.             }
  50.             sort(v.begin(), v.end());
  51.             for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  52.             return true;
  53.         }
  54.         ost += mas[i].first;
  55.         if(ost >= 2016) ost -= 2016;
  56.     }
  57.     if(ost == 0) {
  58.         vector<int> v;
  59.         for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
  60.         sort(v.begin(), v.end());
  61.         for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  62.         return true;
  63.     }
  64.     for(int i = 0; i < 2016; i++) {
  65.         int r = rand() % (n-2016) + 2016;
  66.         ost -= mas[i].first;
  67.         ost += mas[r].first;
  68.         swap(mas[i], mas[r]);
  69.         if(ost < 0) ost += 2016;
  70.         if(ost >= 2016) ost -= 2016;
  71.  
  72.         if(ost == 0) {
  73.             vector<int> v;
  74.             for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
  75.             sort(v.begin(), v.end());
  76.             for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  77.             return true;
  78.         }
  79.     }
  80.     return false;
  81. }
  82.  
  83. const int magic = 1000000;
  84.  
  85. bool my_shuffle2() {
  86.     random_shuffle(mas, mas + n);
  87.     int ost = 0;
  88.     for(int i = 0; i < 2016; i++) {
  89.         if(ost == 0 && i + cnt > 2015) {
  90.             vector<int> v;
  91.             for(int j = 0; j < i; j++) v.pb(mas[j].second);
  92.             while(sz(v) < 2016) {
  93.                 v.pb(idx2016.back());
  94.                 idx2016.pop_back();
  95.             }
  96.             sort(v.begin(), v.end());
  97.             for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  98.             return true;
  99.         }
  100.         ost += mas[i].first;
  101.         if(ost >= 2016) ost -= 2016;
  102.     }
  103.     if(ost == 0) {
  104.         vector<int> v;
  105.         for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
  106.         sort(v.begin(), v.end());
  107.         for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  108.         return true;
  109.     }
  110.     for(int i = 0; i < magic; i++) {
  111.         int r1 = rand() % 2016;
  112.         int r2 = rand() % (n-2016) + 2016;
  113.         int val1 = mas[r1].first;
  114.         int val2 = mas[r2].first;
  115.         if(val1 <= val2) continue;
  116.         ost -= mas[r1].first;
  117.         ost += mas[r2].first;
  118.         swap(mas[r1], mas[r2]);
  119.         if(ost < 0) ost += 2016;
  120.         if(ost >= 2016) ost -= 2016;
  121.  
  122.         if(ost == 0) {
  123.             vector<int> v;
  124.             for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
  125.             sort(v.begin(), v.end());
  126.             for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
  127.             return true;
  128.         }
  129.     }
  130.     return false;
  131. }
  132.  
  133. int main()
  134. {
  135.     //freopen("input.txt","rt",stdin);
  136.     //freopen("output.txt","wt",stdout);
  137.     //freopen("operation.in","rt",stdin);
  138.     //freopen("operation.out","wt",stdout);
  139.     srand(time(0));
  140.     int idx = 0;
  141.     for(int i = 0; i < n; i++) {
  142.         scanf("%d", &mas[i].first);
  143.         //mas[i].first = 1;
  144.         //mas[i].first = rand()%3+2012;
  145.  
  146.  
  147.         mas[i].second = idx + 1;
  148.         if(mas[i].first == 2016) {
  149.             cnt++;
  150.             idx2016.pb(idx + 1);
  151.             i--;
  152.             n--;
  153.         }
  154.         idx++;
  155.     }
  156.     while(clock() * 1e-6 < 0.3) {
  157.         if(my_shuffle()) return 0;
  158.     }
  159.     while(true) {
  160.         if(my_shuffle2()) return 0;
  161.     }
  162.  
  163.     return 0;
  164. }
Advertisement
Add Comment
Please, Sign In to add comment