이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define maxn 1000005
#define pii pair<int, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
ll a[maxn], pref[maxn], val[maxn];
ll out[3 * maxn];
bool ed[3 * maxn];
int main() {
io
ll n, k;
cin >> n >> k;
ll m = 0;
for (int i = 0;i < n;i++) {
cin >> a[i];
m += a[i];
pref[i] = m;
}
bool poss = m % k == 0;
ll siz = m / k;
int vs = 0;
for (int i = 0;i < n;i++) {
if (a[i] > siz) {
poss = false;
break;
}
val[vs++] = pref[i] % siz;
}
val[vs++] = siz;
sort(val, val + vs);
if (!poss) {
cout << -1 << endl;
} else {
int num = 0, cnt = 0;
ll cur = 0;
for (int i = 0;i < vs;i++) {
//cout << val[i] << " " << cur << endl;
if (val[i] - cur > 0) { //[cur, val[i])
out[num++] = val[i] - cur;
int ind = upper_bound(pref, pref + n, cur) - pref;
for (ll j = cur;j < m;j += m / k) {
ind = upper_bound(pref, pref + n, j) - pref;
if (ind < n) out[num++] = ind+1;
}
ed[num - 1] = true;
cur = val[i];
cnt++;
}
}
cout << cnt << "\n";
for (int i = 0;i < num;i++) {
cout << out[i] << (ed[i] ? '\n' : ' ');
}
}
}
/*
4 2
2 3 3 2
6 4
4 1 3 5 5 2
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |