Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2016;
- const int A = 63;
- const int B = 32;
- int a[7777];
- int pr[144][144][144];
- vector <int> get_heap(vector <int> idx, int md) {
- int n = idx.size();
- assert(n == 2 * md - 1);
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= md; j++) {
- for (int rm = 0; rm < md; rm++) {
- pr[i][j][rm] = -1;
- }
- }
- }
- pr[0][0][0] = 0;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j <= md; j++) {
- for (int rm = 0; rm < md; rm++) {
- if (pr[i][j][rm] == -1) {
- continue;
- }
- if (pr[i + 1][j][rm] == -1) {
- pr[i + 1][j][rm] = 0;
- }
- if (j < md) {
- int nrm = (rm + a[idx[i]]) % md;
- if (pr[i + 1][j + 1][nrm] == -1) {
- pr[i + 1][j + 1][nrm] = 1;
- }
- }
- }
- }
- }
- assert(pr[n][md][0] != -1);
- vector <int> ret;
- int j = md, rm = 0;
- for (int i = n; i > 0; i--) {
- if (pr[i][j][rm] == 1) {
- ret.push_back(idx[i - 1]);
- j--;
- rm = ((rm - a[idx[i - 1]]) % md + md) % md;
- }
- }
- assert(ret.size() == md);
- return ret;
- }
- vector <int> heap[7777];
- int main() {
- int cnt = 6666;
- vector <int> idx(cnt);
- for (int i = 0; i < cnt; i++) {
- scanf("%d", &a[i]);
- idx[i] = i;
- }
- for (int id = 0; id < 2 * B - 1; id++) {
- vector <int> b;
- for (int i = 0; i < 2 * A - 1; i++) {
- b.push_back(idx.back());
- idx.pop_back();
- }
- heap[id] = get_heap(b, A);
- for (int i = 0; i < (int) b.size(); i++) {
- bool used = false;
- for (int j = 0; j < (int) heap[id].size(); j++) {
- if (b[i] == heap[id][j]) {
- used = true;
- break;
- }
- }
- if (!used) {
- idx.push_back(b[i]);
- }
- }
- }
- for (int id = 0; id < 2 * B - 1; id++) {
- int sum = 0;
- for (int j = 0; j < (int) heap[id].size(); j++) {
- sum += a[heap[id][j]];
- }
- a[cnt + id] = sum;
- }
- vector <int> fake;
- for (int id = 0; id < 2 * B - 1; id++) {
- fake.push_back(cnt + id);
- }
- vector <int> heaps = get_heap(fake, B);
- vector <int> res;
- for (int i = 0; i < (int) heaps.size(); i++) {
- for (int j = 0; j < (int) heap[heaps[i] - cnt].size(); j++) {
- res.push_back(heap[heaps[i] - cnt][j]);
- }
- }
- sort(res.begin(), res.end());
- int total = 0;
- for (int i = 0; i < (int) res.size(); i++) {
- total += a[res[i]];
- }
- assert(total % N == 0);
- for (int i = 0; i < (int) res.size(); i++) {
- printf("%d\n", res[i] + 1);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment