Submission #1033998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033998		denislav	DEL13 (info1cup18_del13)	C++17	6 / 100	4 ms	1372 KiB

del13

# include <iostream>
# include <vector>
using namespace std;

const int MAX=2e5+11;

int n,q,m;
int a[MAX];
bool used[MAX];
vector<int> v;

void read()
{
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>a[i];
        used[a[i]]=1;
    }
}

void print_moves()
{
    cout<<0<<"\n";

    /*
    cout<<v.size()<<"\n";
    for(int x: v) cout<<x<<" ";
    cout<<"\n";
    */
}

void doit(int l, int r)
{
    //cout<<l<<" "<<r<<"\n";

    int sz=(r-l+1);
    int cut=(l+r)/2;
    while(sz>2)
    {
        sz-=2;
        v.push_back(cut);
    }
}

bool alone[MAX];
bool f=1;
vector<pair<int,int>> len;

void doit2(vector<pair<int, int>> curr)
{
    vector<bool> rem((int)curr.size());
    for(int i=0;i<(int)curr.size()-1;i++)
    {
        //cout<<"->"<<curr[i].first<<" "<<curr[i].second<<"\n";
        //if(i==0) cout<<"-->"<<curr[i+1].first<<" "<<curr[i+1].second<<"\n";

        if(curr[i].second<0) {f=0;return ;}
        if(rem[i]==1 and rem[i]%2==0) continue;

        if(curr[i].second%2==0)
        {
            rem[i]=1;
            rem[i+1]=1;
            curr[i].second-=2;
            curr[i+1].second-=2;
        }
        else
        {
            rem[i]=1;
            rem[i+1]=1;
            curr[i].second--;
            curr[i+1].second--;
        }

        if(curr[i].second<0) {f=0;return ;}
    }

    int sz=curr.size()-1;
    if(curr[sz].second<0) {f=0;return ;}
    if(rem[sz] and curr[sz].second%2==0) return ;
    if(curr[sz].second%2==0)
    {
        if(curr[sz-1].second%2==0)
        {
            if(curr[sz-1].second>=2 and curr[sz].second>=2) return ;
            else {f=0;return ;}
        }
        else {f=0;return ;}
    }
    else
    {
        if(curr[sz-1].second%2!=0)
        {
            if(curr[sz-1].second>=1 and curr[sz].second>=1) return ;
            else {f=0;return ;}
        }
        else {f=0;return ;}
    }

    //cout<<"\n";
}

void solve()
{
    if(n==q) {cout<<0<<"\n";return ;}

    int start=-1;
    for(int i=1;i<=n;i++)
    {
        if(used[i]==0)
        {
            if(start==-1) start=i;
        }
        else
        {
            if(start!=-1) len.push_back({start,i-1});
            start=-1;
        }
    }
    if(start!=-1) len.push_back({start,n});

    int m=len.size();
    vector<int> sz;
    for(int i=0;i<m;i++)
    {
        //cout<<i<<":"<<len[i].first<<" "<<len[i].second<<"\n";

        //doit(len[i].first,len[i].second);
        //int p=(len[i].second-len[i].first+1)%2;
        //if(p==0) p+=2;
        sz.push_back(len[i].second-len[i].first+1);

        //cout<<sz.back()<<"\n";

        if(i>0 and len[i-1].second+2==len[i].first)
        {
            alone[i-1]=0;
            alone[i]=0;
        }
    }
    for(int i=0;i<m;i++) if(alone[i]) {cout<<-1<<"\n";return ;}

    vector<pair<int, int>> curr;
    for(int i=0;i<m;i++)
    {
        if(i>0 and len[i-1].second+2==len[i].first)
        {
            curr.push_back({i,sz[i]});
        }
        else
        {
            if((int)curr.size()>0) doit2(curr);

            curr.clear();
            curr.push_back({i,sz[i]});
        }
    }

    if((int)curr.size()>0) doit2(curr);


    if(f) print_moves();
    else cout<<-1<<"\n";
}

void reset()
{
    f=1;
    v.clear();
    len.clear();
    for(int i=1;i<=n;i++) used[i]=0;
    for(int i=0;i<=n;i++) alone[i]=1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;
    cin>>t;
    while(t--)
    {
        reset();
        read();
        solve();
    }

    return 0;
}

/**
3
5 1
3
7 3
1 5 7
7 3
1 2 7
*/


/**
1
5 1
3
*/

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