oj.uz

Submission #137463

# Submission time Handle Problem Language Result Execution time Memory
137463 2019-07-27T20:24:43 Z vardan__02 Gift (IZhO18_nicegift) C++14
49 / 100
 2000 ms 143732 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB n=4
2 Correct 71 ms 70776 KB n=3
3 Correct 67 ms 70776 KB n=3
4 Correct 67 ms 70904 KB n=4
5 Correct 67 ms 70776 KB n=4
6 Correct 67 ms 70776 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB n=4
2 Correct 71 ms 70776 KB n=3
3 Correct 67 ms 70776 KB n=3
4 Correct 67 ms 70904 KB n=4
5 Correct 67 ms 70776 KB n=4
6 Correct 67 ms 70776 KB n=2
7 Correct 66 ms 70776 KB n=5
8 Correct 68 ms 71288 KB n=8
9 Correct 109 ms 71632 KB n=14
10 Correct 92 ms 71416 KB n=11
11 Correct 1361 ms 75128 KB n=50000
12 Correct 1054 ms 75284 KB n=50000
13 Correct 217 ms 73592 KB n=10
14 Correct 213 ms 73180 KB n=685
15 Correct 225 ms 73468 KB n=623
16 Correct 160 ms 72284 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB n=4
2 Correct 71 ms 70776 KB n=3
3 Correct 67 ms 70776 KB n=3
4 Correct 67 ms 70904 KB n=4
5 Correct 67 ms 70776 KB n=4
6 Correct 67 ms 70776 KB n=2
7 Correct 66 ms 70776 KB n=5
8 Correct 68 ms 71288 KB n=8
9 Correct 109 ms 71632 KB n=14
10 Correct 92 ms 71416 KB n=11
11 Correct 1361 ms 75128 KB n=50000
12 Correct 1054 ms 75284 KB n=50000
13 Correct 217 ms 73592 KB n=10
14 Correct 213 ms 73180 KB n=685
15 Correct 225 ms 73468 KB n=623
16 Correct 160 ms 72284 KB n=973
17 Correct 185 ms 72744 KB n=989
18 Correct 108 ms 72140 KB n=563
19 Correct 92 ms 72356 KB n=592
20 Correct 112 ms 72028 KB n=938
21 Correct 98 ms 72060 KB n=747
22 Correct 103 ms 72112 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1729 ms 109588 KB n=1000000
2 Correct 873 ms 95252 KB n=666666
3 Correct 405 ms 84732 KB n=400000
4 Correct 272 ms 80632 KB n=285714
5 Correct 74 ms 71644 KB n=20000
6 Correct 172 ms 77040 KB n=181818
7 Correct 69 ms 71288 KB n=10000
8 Correct 83 ms 71672 KB n=6666
9 Correct 69 ms 71032 KB n=4000
10 Correct 109 ms 72952 KB n=2857
11 Correct 82 ms 71032 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB n=4
2 Correct 71 ms 70776 KB n=3
3 Correct 67 ms 70776 KB n=3
4 Correct 67 ms 70904 KB n=4
5 Correct 67 ms 70776 KB n=4
6 Correct 67 ms 70776 KB n=2
7 Correct 66 ms 70776 KB n=5
8 Correct 68 ms 71288 KB n=8
9 Correct 109 ms 71632 KB n=14
10 Correct 92 ms 71416 KB n=11
11 Correct 1361 ms 75128 KB n=50000
12 Correct 1054 ms 75284 KB n=50000
13 Correct 217 ms 73592 KB n=10
14 Correct 213 ms 73180 KB n=685
15 Correct 225 ms 73468 KB n=623
16 Correct 160 ms 72284 KB n=973
17 Correct 185 ms 72744 KB n=989
18 Correct 108 ms 72140 KB n=563
19 Correct 92 ms 72356 KB n=592
20 Correct 112 ms 72028 KB n=938
21 Correct 98 ms 72060 KB n=747
22 Correct 103 ms 72112 KB n=991
23 Correct 1729 ms 109588 KB n=1000000
24 Correct 873 ms 95252 KB n=666666
25 Correct 405 ms 84732 KB n=400000
26 Correct 272 ms 80632 KB n=285714
27 Correct 74 ms 71644 KB n=20000
28 Correct 172 ms 77040 KB n=181818
29 Correct 69 ms 71288 KB n=10000
30 Correct 83 ms 71672 KB n=6666
31 Correct 69 ms 71032 KB n=4000
32 Correct 109 ms 72952 KB n=2857
33 Correct 82 ms 71032 KB n=2000
34 Execution timed out 2044 ms 143732 KB Time limit exceeded
35 Halted 0 ms 0 KB -