fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  8. typedef long long LL;
  9. typedef pair<int, int> PII;
  10.  
  11. int n;
  12. int d[4100][4100];
  13. vector<int> ind[31];
  14. int rev[405], ans[405], sub[405];
  15. vector<int> v[3];
  16.  
  17. int main() {
  18.     //freopen("input.txt", "r", stdin);
  19.     scanf("%d", &n);
  20.     int tot = 0;
  21.     REP(i, n) {
  22.         int x;
  23.         scanf("%d", &x);
  24.         sub[i] = x;
  25.         tot += x;
  26.         ind[x].pb(i);
  27.     }
  28.     memset(d, -1, sizeof d);
  29.     d[0][0] = 0;
  30.     int sum = 1;
  31.     for (int i = 1; i <= 30; ++i) {
  32.         int sz = (int)ind[i].size();
  33.         sum = min(4100, sum + i * sz);
  34.         memset(rev, -1, sizeof rev);
  35.         REP(j, ind[i].size()) rev[ind[i][j]] = j;
  36.         REP(x, sum) REP(y, sum) if (d[x][y] != -1) {
  37.             int z = rev[d[x][y] >> 1] + 1;
  38.             if (z == sz) continue;
  39.             if (x + i < 4100 && (d[x + i][y] == -1 || rev[d[x + i][y] >> 1] > z)) {
  40.                 d[x + i][y] = ind[i][z] << 1;
  41.             }
  42.             if (y + i < 4100 && (d[x][y + i] == -1 || rev[d[x][y + i] >> 1] > z)) {
  43.                 d[x][y + i] = 1 | (ind[i][z] << 1);
  44.             }
  45.         }
  46.     }
  47.     int bi, bj, best;
  48.     bi = bj = -1;
  49.     best = 12341234;
  50.     REP(i, 4100) REP(j, 4100) if (d[i][j] != -1) {
  51.         int k = tot - i - j;
  52.         int mn = min(min(i, j), k);
  53.         int mx = max(max(i, j), k);
  54.         if (mx - mn < best) {
  55.             best = mx - mn;
  56.             bi = i;
  57.             bj = j;
  58.         }
  59.     }
  60.     REP(i, n) ans[i] = 2;
  61.     for (int i = bi, j = bj; i || j; ) {
  62.         int q = d[i][j] >> 1;
  63.         int w = d[i][j] & 1;
  64.         ans[q] = w;
  65.         if (w) j -= sub[q];
  66.         else i -= sub[q];
  67.     }
  68.     REP(i, n) v[ans[i]].pb(i + 1);
  69.     printf("%d\n", best);
  70.     REP(i, 3) {
  71.         printf("%d", (int)v[i].size());
  72.         for (int x : v[i]) printf(" %d", x);
  73.         printf("\n");
  74.     }
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.1s 69120KB
comments (?)
stdin
copy 
6
7 3 20 1 5 7
stdout
copy 
9
3 2 4 6
2 1 5
1 3
https://ideone.com/elPSXb
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!