oj.uz

Submission #1033896

# Submission time Handle Problem Language Result Execution time Memory
1033896 2024-07-25T07:38:58 Z denislav DEL13 (info1cup18_del13) C++17
15 / 100
 4 ms 1368 KB 
# 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<<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];

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

    vector<pair<int,int>> len;
    vector<int> sz;
    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();
    for(int i=0;i<m;i++)
    {
        sz.push_back(len[i].second-len[i].first+1);
        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 ;}

    if(sz[0]%2!=sz[1]%2) {cout<<-1<<"\n";return ;}

    doit(len[0].first,len[0].second);
    doit(len[1].first,len[1].second);
    int mid=len[0].second+1;
    if(sz[0]%2==0) {v.push_back(mid);v.push_back(mid);}
    else v.push_back(mid);

    print_moves();
}

void reset()
{
    v.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
*/

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Incorrect 2 ms 412 KB Output isn't correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Incorrect 2 ms 412 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Incorrect 2 ms 412 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 3 ms 860 KB Output isn't correct
9 Incorrect 3 ms 1116 KB Output isn't correct
10 Incorrect 4 ms 1116 KB Output isn't correct
11 Incorrect 4 ms 1368 KB Output isn't correct