Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <list>
- #include <map>
- #include <set>
- #include <stdlib.h>
- #include <sstream>
- #include <assert.h>
- #include <memory.h>
- #include <string.h>
- #include <time.h>
- using namespace std;
- #pragma comment(linker, "/STACK:100000000")
- #define mp make_pair
- #define pb push_back
- #define ll long long
- #define ull long long
- #define sz(x) (int)(x).size()
- #define fr(i,a,b) for(int i = (a);i <= (b);i++)
- #define fd(i,a,b) for(int i = (a);i >= (b);i--)
- int ri(){int x;scanf("%d",&x);return x;}
- pair<int, int> mas[7777];
- int cnt = 0;
- vector<int> idx2016;
- int n = 6666;
- bool my_shuffle() {
- random_shuffle(mas, mas + n);
- int ost = 0;
- for(int i = 0; i < 2016; i++) {
- if(ost == 0 && i + cnt > 2015) {
- vector<int> v;
- for(int j = 0; j < i; j++) v.pb(mas[j].second);
- while(sz(v) < 2016) {
- v.pb(idx2016.back());
- idx2016.pop_back();
- }
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- ost += mas[i].first;
- if(ost >= 2016) ost -= 2016;
- }
- if(ost == 0) {
- vector<int> v;
- for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- for(int i = 0; i < 2016; i++) {
- int r = rand() % (n-2016) + 2016;
- ost -= mas[i].first;
- ost += mas[r].first;
- swap(mas[i], mas[r]);
- if(ost < 0) ost += 2016;
- if(ost >= 2016) ost -= 2016;
- if(ost == 0) {
- vector<int> v;
- for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- }
- return false;
- }
- const int magic = 1000000;
- bool my_shuffle2() {
- random_shuffle(mas, mas + n);
- int ost = 0;
- for(int i = 0; i < 2016; i++) {
- if(ost == 0 && i + cnt > 2015) {
- vector<int> v;
- for(int j = 0; j < i; j++) v.pb(mas[j].second);
- while(sz(v) < 2016) {
- v.pb(idx2016.back());
- idx2016.pop_back();
- }
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- ost += mas[i].first;
- if(ost >= 2016) ost -= 2016;
- }
- if(ost == 0) {
- vector<int> v;
- for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- for(int i = 0; i < magic; i++) {
- int r1 = rand() % 2016;
- int r2 = rand() % (n-2016) + 2016;
- int val1 = mas[r1].first;
- int val2 = mas[r2].first;
- if(val1 <= val2) continue;
- ost -= mas[r1].first;
- ost += mas[r2].first;
- swap(mas[r1], mas[r2]);
- if(ost < 0) ost += 2016;
- if(ost >= 2016) ost -= 2016;
- if(ost == 0) {
- vector<int> v;
- for(int i = 0; i < 2016; i++) v.pb(mas[i].second);
- sort(v.begin(), v.end());
- for(int i = 0; i < 2016; i++) printf("%d\n", v[i]);
- return true;
- }
- }
- return false;
- }
- int main()
- {
- //freopen("input.txt","rt",stdin);
- //freopen("output.txt","wt",stdout);
- //freopen("operation.in","rt",stdin);
- //freopen("operation.out","wt",stdout);
- srand(time(0));
- int idx = 0;
- for(int i = 0; i < n; i++) {
- scanf("%d", &mas[i].first);
- //mas[i].first = 1;
- //mas[i].first = rand()%3+2012;
- mas[i].second = idx + 1;
- if(mas[i].first == 2016) {
- cnt++;
- idx2016.pb(idx + 1);
- i--;
- n--;
- }
- idx++;
- }
- while(clock() * 1e-6 < 0.3) {
- if(my_shuffle()) return 0;
- }
- while(true) {
- if(my_shuffle2()) return 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment