Submission #521648

#	Time	Username	Problem	Language	Result	Execution time	Memory
521648		lucri	DEL13 (info1cup18_del13)	C++17	30 / 100	22 ms	2320 KiB

del13

#include <iostream>
#include <fstream>
using namespace std;
long long t,n,f[200010],q,ans[200010];
struct blocuri{long long poz,nrs,fmax;}a[200010];
ofstream out("fisier.txt");
//ifstream in("ceva.txt");
int main()
{
    cin>>t;
    while(t--)
    {
        ans[0]=0;
        cin>>n>>q;
        for(long long i=2;i<=q+1;++i)
            cin>>f[i];
        f[q+2]=n+1;
        a[q+2].fmax=0;
        a[q+2].poz=0;
        a[q+2].nrs=0;
        a[q+3].fmax=0;
        a[q+3].poz=0;
        a[q+3].nrs=0;
        a[0].fmax=0;
        a[0].poz=0;
        a[0].nrs=0;
        a[q+1].fmax=0;
        a[q+1].poz=0;
        a[q+1].nrs=0;
        a[1].fmax=0;
        a[1].poz=0;
        a[1].nrs=0;
        f[1]=0;
        ++q;
        for(long long i=1;i<=q;++i)
        {
            a[i].poz=(f[i]+f[i+1])/2;
            if(f[i+1]-f[i]<=3)
            {
                a[i].nrs=0;
                a[i].fmax=f[i+1]-f[i]-1;
            }
            else
            {
                a[i].nrs=(f[i+1]-f[i]-4)/2;
                if((f[i+1]-f[i])%2==0)
                    a[i].fmax=3;
                else
                    a[i].fmax=4;
            }
            for(long long j=1;j<=a[i].nrs;++j)
                ans[++ans[0]]=a[i].poz;
        }
        for(long long i=1;i<=q;++i)
        {
            if(a[i-1].fmax==0&&a[i].fmax!=0&&a[i+1].fmax==0)
                ans[0]=-1;
            else if(a[i-1].fmax==0&&a[i].fmax!=0)
            {
                if(a[i].fmax>2)
                {
                    a[i].fmax-=2;
                    ans[++ans[0]]=a[i].poz;
                }
            }
            else if(a[i].fmax!=0)
            {
                a[i].fmax-=a[i-1].fmax;
                if(a[i].fmax<0)
                {
                    out<<f[i+1]<<'\n';
                    ans[0]=-1;
                }
                else if(a[i+1].fmax==0)
                {
                    if(a[i].fmax==2&&a[i-1].fmax!=0)
                    {
                        a[i].fmax-=2;
                        ans[++ans[0]]=a[i].poz;
                    }
                    else if(a[i].fmax!=0)
                    {
                        out<<f[i+1]<<'\n';
                        ans[0]=-1;
                    }
                }
                if(ans[0]>=0&&a[i].fmax>2)
                {
                    ans[++ans[0]]=a[i].poz;
                    a[i].fmax-=2;
                }
                if(a[i+1].fmax==1)
                {
                    if(a[i].fmax==2)
                    {
                        if(a[i-1].fmax!=0)
                        {
                            a[i].fmax-=2;
                            ans[++ans[0]]=a[i].poz;
                        }
                        else
                            ans[0]=-1;
                    }
                }
                if(a[i].fmax==2&&a[i+1].fmax==2&&a[i+2].fmax>=2)
                {
                    int q=0;
                    if(a[i-1].fmax!=0)
                    {
                        for(;a[i+q].fmax!=2&&a[i+q].fmax!=4;++q);
                        if(q%2==0)
                        {
                            a[i].fmax-=2;
                            ans[++ans[0]]=a[i].poz;
                        }
                    }
                }
                if(ans[0]>=0)
                    for(long long j=0;j<a[i-1].fmax;++j)
                        ans[++ans[0]]=f[i];
            }
            if(ans[0]<0)
                break;
        }
        cout<<ans[0]<<'\n';
        if(ans[0]==-1)
            out<<ans[0]<<'\n';
        else
            out<<1<<'\n';
        for(long long i=1;i<=ans[0];++i)
            cout<<ans[i]<<' ';
        if(ans[0]>0)
            cout<<'\n';
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30