# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
386860 | vanic | Gift (IZhO18_nicegift) | C++14 | 2085 ms | 123712 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll a[maxn];
ll sum;
pair < ll, int > v[maxn*4];
set < int > cur;
int main(){
int n, k;
scanf("%d%d", &n, &k);
for(int i=0; i<n; ++i){
scanf("%lld", a+i);
sum+=a[i];
}
if(sum%k){
printf("-1\n");
return 0;
}
sum/=k;
for(int i=0; i<n; ++i){
if(a[i]>sum){
printf("-1\n");
return 0;
}
}
int pos=0;
int iduc;
int br=0;
for(int i=0; i<n; ++i){
iduc=pos+a[i];
if(iduc>sum){
v[br]={pos, i+1};
++br;
iduc-=sum;
pos=0;
}
v[br]={pos, i+1};
++br;
if(iduc!=sum){
v[br]={iduc, -i-1};
++br;
}
else{
iduc=0;
}
pos=iduc;
}
v[br]={sum, 0};
++br;
sort(v, v+br);
int sol=0;
for(int i=0; i<br-1; ++i){
if(v[i].first!=v[i+1].first){
++sol;
}
}
printf("%d\n", sol);
for(int i=0; i<br-1; ++i){
if(v[i].second>0){
cur.insert(v[i].second);
}
else{
cur.erase(-v[i].second);
}
if(v[i].first==v[i+1].first){
continue;
}
printf("%lld ", v[i+1].first-v[i].first);
for(int x : cur){
printf("%d ", x);
}
printf("\n");
}
return 0;
}
Compilation message (stderr)
# | 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... |