Advertisement
BaoJIaoPisu

Untitled

Sep 27th, 2021
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair<int,int>
  5. #define fr first
  6. #define sc second
  7. #define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  8. //#define PROBLEM            ""
  9. /*   /\_/\
  10.     (= ._.)
  11.     / >?  \>$
  12. */
  13. const int maxn = 1e6+3;
  14. ll sum, s[maxn];
  15. int n, k, a[maxn];
  16. int id[maxn];
  17. bool cal(int i, int j) {
  18.     if (s[i] == sum) {
  19.         if (i == k) return true;
  20.         return cal(i+1, n);
  21.     }
  22.     ll tmp;
  23.     for (int z = j; z > 0; --z) {
  24.         if (id[z]) continue;
  25.         tmp = s[i] + a[z];
  26.         if (tmp <= sum) {
  27.             id[z] = i; s[i] += a[z];
  28.             bool check = cal(i, z-1);
  29.             if (check) return true;
  30.             id[z] = 0; s[i] -= a[z];
  31.         }
  32.     }
  33.     return false;
  34. }
  35.  
  36. int main()
  37. {
  38.     camnguyenmeow;
  39.     #ifdef PROBLEM
  40.         freopen(PROBLEM".inp","r",stdin);
  41.         freopen(PROBLEM".out","w",stdout);
  42.     #endif
  43.     cin >> n >> k;
  44.     for (int i = 1; i <= n; ++i) {
  45.         cin >> a[i]; sum += a[i];
  46.     }
  47.     if (sum % k != 0) {cout << -1; return 0;}
  48.     if (k == 1) {for (int i = 1; i <= n; ++i) cout << 1; return 0;}
  49.     sum/=k;
  50.     s[1] = a[n]; id[n] = 1;
  51.     bool ok = cal(1, n);
  52.     if (!ok) {cout << -1; return 0;}
  53.     for (int i = 1; i <= n; ++i) cout << id[i] <<' ';
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement