# Untitled

Sep 27th, 2021
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }