Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pii pair<int,int>
- #define fr first
- #define sc second
- #define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- //#define PROBLEM ""
- /* /\_/\
- (= ._.)
- / >? \>$
- */
- const int maxn = 1e6+3;
- ll sum, s[maxn];
- int n, k, a[maxn];
- int id[maxn];
- bool cal(int i, int j) {
- if (s[i] == sum) {
- if (i == k) return true;
- return cal(i+1, n);
- }
- ll tmp;
- for (int z = j; z > 0; --z) {
- if (id[z]) continue;
- tmp = s[i] + a[z];
- if (tmp <= sum) {
- id[z] = i; s[i] += a[z];
- bool check = cal(i, z-1);
- if (check) return true;
- id[z] = 0; s[i] -= a[z];
- }
- }
- return false;
- }
- int main()
- {
- camnguyenmeow;
- #ifdef PROBLEM
- freopen(PROBLEM".inp","r",stdin);
- freopen(PROBLEM".out","w",stdout);
- #endif
- cin >> n >> k;
- for (int i = 1; i <= n; ++i) {
- cin >> a[i]; sum += a[i];
- }
- if (sum % k != 0) {cout << -1; return 0;}
- if (k == 1) {for (int i = 1; i <= n; ++i) cout << 1; return 0;}
- sum/=k;
- s[1] = a[n]; id[n] = 1;
- bool ok = cal(1, n);
- if (!ok) {cout << -1; return 0;}
- for (int i = 1; i <= n; ++i) cout << id[i] <<' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement