# include <iostream>
# include <vector>
# include <tuple>
using namespace std;
const int MAX=2e5+11;
int n,q,m;
int a[MAX];
bool used[MAX];
vector<int> premoves;
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<<premoves.size()+v.size()<<"\n";
for(int x: premoves) cout<<x<<" ";
for(int x: v) cout<<x<<" ";
cout<<"\n";
}
int doit(int l, int r)
{
//cout<<l<<" "<<r<<"\n";
int sz=(r-l+1);
int cut=(l+r)/2;
while(sz>4)
{
sz-=2;
premoves.push_back(cut);
}
return sz;
}
bool alone[MAX];
bool f=1;
vector<pair<int,int>> len;
bool dp[MAX][6][2];
tuple<int, int, int> pr[MAX][6][2];
void doit2(vector<pair<int, int>> curr)
{
int sz=curr.size();
for(int i=0;i<sz;i++)
{
for(int k=0;k<=4;k++)
{
dp[i][k][0]=dp[i][k][1]=0;
pr[i][k][0]=pr[i][k][1]=make_tuple(0,0,0);
}
}
dp[0][curr[0].second][0]=1;pr[0][curr[0].second][0]=make_tuple(0,0,0);
for(int i=0;i<sz-1;i++)
{
for(int f=0;f<=1;f++)
{
for(int k=0;k<=4;k++)
{
if(dp[i][k][f]==0) continue;
//cout<<"->"<<i<<" "<<k<<" "<<f<<"\n";
if(f==0 or (f==1 and k%2!=0))
{
if(k%2==1)
{
if(k>=1 and curr[i+1].second>=1) {dp[i+1][curr[i+1].second-1][1]=1;pr[i+1][curr[i+1].second-1][1]=make_tuple(1,k,f);}
}
else if(k%2==0)
{
if(k>=2 and curr[i+1].second>=2) {dp[i+1][curr[i+1].second-2][1]=1;pr[i+1][curr[i+1].second-2][1]=make_tuple(2,k,f);}
}
}
else if(f==1)
{
dp[i+1][curr[i+1].second][0]=1;pr[i+1][curr[i+1].second][0]=make_tuple(0,k,f);
if(curr[i+1].second%2==1 and curr[i+1].second>=1 and k>=1 and k%2==1) {dp[i+1][curr[i+1].second-1][1]=1;pr[i+1][curr[i+1].second-1][1]=make_tuple(1,k,f);}
if(curr[i+1].second%2==0 and curr[i+1].second>=2 and k>=2 and k%2==0) {dp[i+1][curr[i+1].second-2][1]=1;pr[i+1][curr[i+1].second-2][1]=make_tuple(2,k,f);}
}
}
}
}
if(!(dp[sz-1][0][1] or dp[sz-1][2][1] or dp[sz-1][4][1])) {f=0;return ;}
int u=sz-1, k=0, f=1;
if(dp[u][0][1]) k=0;
else if(dp[u][2][1]) k=2;
else if(dp[u][4][1]) k=4;
while(u>=0)
{
//cout<<u<<" "<<k<<" "<<f<<"\n";
int tm, k2, f2;
tie(tm,k2,f2)=pr[u][k][f];
for(int i=1;i<=tm;i++)
{
v.push_back(len[curr[u].first].first-1);
curr[u].second--;
curr[u-1].second--;
}
for(int i=1;i<=curr[u].second/2;i++) premoves.push_back((len[curr[u].first].first+len[curr[u].first].second)/2);
u--;
k=k2;
f=f2;
}
}
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(doit(len[i].first,len[i].second));
//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;
premoves.clear();
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
*/
/**
1
12 4
1 4 9 12
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
412 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1500 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1884 KB |
Output is correct |
