#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
ll n,k,a[1000005],m,i,j,p,q,t,u,v;
struct anun
{
ll kod,x;
};
bool operator<(const anun &a, const anun & b)
{
return a.x<b.x;
}
anun b[1000005];
vector<ll> ans[3000005];
void entaxndir4()
{
if(n%k!=0)
{
if(a[1]%k!=0)
{
if(n*a[1]%k!=0)
cout<<-1<<endl;
else
{
p=k+n%k;
if(a[n]>k)
m=n/k-1+p+p/2;
else
m=n/k-1+p/2;
cout<<m<<endl;
v=a[n]/k;
if(a[n]>k)
{
for(i=1;i<=p;i++)
{
cout<<v<<" ";
q=k;
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(j<=p && q!=0)
{
a[j]-=v;
cout<<j<<" ";
j++;
q--;
}
if(q!=0)
{
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(q!=0 && j<=p)
{
a[j]-=v;
cout<<j<<" ";
j++;
q--;
}
}
cout<<endl;
}
}
for(i=1;i<=p/2;i++)
{
cout<<1<<" ";
q=k;
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(j<=p && q!=0)
{
a[j]--;
cout<<j<<" ";
j++;
q--;
}
if(q!=0)
{
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(q!=0 && j<=p)
{
a[j]--;
cout<<j<<" ";
j++;
q--;
}
}
cout<<endl;
}
for(i=p+1;i<=n;i++)
{
if((i-p)%k==1)
cout<<a[n]<<" ";
cout<<i<<" ";
if((i-p)%k==0)
cout<<endl;
}
}
}
else
{
p=k+n%k;
m=n/k-1+p;
cout<<m<<endl;
v=a[n]/k;
for(i=1;i<=p;i++)
{
cout<<v<<" ";
q=k;
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(j<=p && q!=0)
{
a[j]-=v;
cout<<j<<" ";
j++;
q--;
}
if(q!=0)
{
u=a[p];
j=1;
while(a[j]!=u)
j++;
while(q!=0 && j<=p)
{
a[j]-=v;
cout<<j<<" ";
j++;
q--;
}
}
cout<<endl;
}
for(i=p+1;i<=n;i++)
{
if((i-p)%k==1)
cout<<a[n]<<" ";
cout<<i<<" ";
if((i-p)%k==0)
cout<<endl;
}
}
}
else
{
cout<<n/k<<endl;
cout<<a[1]<<" ";
for(i=1;i<=n;i++)
{
cout<<i<<" ";
if(i%k==0)
{
cout<<endl;
if(i!=n)
cout<<a[1]<<" ";
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
ll sum=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
b[i].x=a[i];
b[i].kod=i;
sum+=a[i];
if(a[i]!=a[1])
t=1;
}
if(t==0)
{
entaxndir4();
return 0;
}
if(sum%k!=0)
{
cout<<-1<<endl;
return 0;
}
sort(b+1,b+1+n);
while(b[n].x!=0)
{
m++;
ans[m].PB(1);
q=k;
u=b[n].x;
j=1;
while(b[j].x!=u)
j++;
while(j<=n && q!=0)
{
b[j].x--;
ans[m].PB(b[j].kod);
j++;
q--;
}
if(q!=0)
{
if(b[n].x==0)
{
cout<<-1<<endl;
return 0;
}
u=b[n].x;
j=1;
while(b[j].x!=u)
j++;
if(j==n)
{
cout<<-1<<endl;
return 0;
}
while(q!=0 && j<=p)
{
b[j].x--;
ans[m].PB(b[j].kod);
j++;
q--;
}
}
}
cout<<m<<endl;
for(i=1;i<=m;i++)
{
for(j=0;j<ans[i].size();j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}
Compilation message
nicegift.cpp: In function 'int main()':
nicegift.cpp:256:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<ans[i].size();j++)
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
70776 KB |
n=4 |
| 2 |
Incorrect |
67 ms |
70776 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
70776 KB |
n=4 |
| 2 |
Incorrect |
67 ms |
70776 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
70776 KB |
n=4 |
| 2 |
Incorrect |
67 ms |
70776 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1724 ms |
109440 KB |
n=1000000 |
| 2 |
Correct |
873 ms |
95212 KB |
n=666666 |
| 3 |
Correct |
407 ms |
84728 KB |
n=400000 |
| 4 |
Correct |
277 ms |
80732 KB |
n=285714 |
| 5 |
Correct |
78 ms |
71676 KB |
n=20000 |
| 6 |
Correct |
186 ms |
76792 KB |
n=181818 |
| 7 |
Correct |
70 ms |
71188 KB |
n=10000 |
| 8 |
Correct |
86 ms |
71672 KB |
n=6666 |
| 9 |
Correct |
68 ms |
70904 KB |
n=4000 |
| 10 |
Correct |
110 ms |
72984 KB |
n=2857 |
| 11 |
Correct |
67 ms |
70904 KB |
n=2000 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
70776 KB |
n=4 |
| 2 |
Incorrect |
67 ms |
70776 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
