Submission #137463

#	Time	Username	Problem	Language	Result	Execution time	Memory
137463		vardan__02	Gift (IZhO18_nicegift)	C++14	49 / 100	2044 ms	143732 KiB

nicegift

#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;
    }
    sort(b+1,b+1+n);
    while(b[n].x!=0)
    {
        t=0;
        m++;
        ans[m].PB(1);
        q=k;
        j=n;
        while(true)
        {
            t=j;
            if(b[j].x==0)
            {
                cout<<-1<<endl;
                return 0;
            }
            v=0;
            u=b[j].x;
            while(b[j].x==u && j>=1)
            {
                v++;
                j--;
            }
            if(v<=q)
            {
                q-=v;
                for(ll l=j+1;l<=t;l++)
                {
                    ans[m].PB(b[l].kod);
                    b[l].x--;
                }
            }
            else
            {
                ll l=j+1;
                while(q!=0)
                {
                    ans[m].PB(b[l].kod);
                    b[l].x--;
                    q--;
                    l++;
                }
            }
            if(q==0)
                break;
        }
    }
    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 (stderr)

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++)
                 ~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 51