fork download
  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
stdin
6
7 3 20 1 5 7
stdout
9
3 2 4 6
2 1 5
1 3