| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1319973 | Petrix | DEL13 (info1cup18_del13) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
int dp[150000][3],p[150000][3],v[150000];
vector<int> a1,a2;
void solve(){
int n,q,i,j,k,aux1,aux2,aux=0,mar;
cin>>n>>q;
for(i=1;i<=q;i++) cin>>v[i];
q++;v[q]=n+1;v[q+1]=n+2;
for(i=0;i<=q+2;i++){
dp[i][0]=dp[i][1]=dp[i][2]=0;
}
dp[0][0]=1;
for(i=1;i<=q;i++){
for(j=0;j<3;j++){
for(k=0;k<3;k++){
aux1=v[i]-v[i-1]-1;
aux2=v[i+1]-v[i]-1;
if((j+k==aux1 && k<=aux2) ||
(j+k<aux1 && (aux1-j+k)%2==0 && k<=aux2 && j+k>0)){
if(!dp[i][k] && dp[i-1][j]==1){
p[i][k]=j;dp[i][k]=1;
}
}
}
}
}
if(!dp[q][0]){
cout<<"-1\n";
return;
}
a1.clear();a2.clear();
aux=0
while(q){
for(i=0;i<aux;i++) a1.push_back(v[q]);
mar=(v[q]-v[q-1]-1-aux-p[q][aux])/2;
for(i=1;i<=mar;i++) a2.push_back(v[q-1]+mar+1);
aux=p[q][aux];q--;
}
cout<<a1.size()+a2.size()<<"\n";
for(auto it:a2) cout<<it<<" ";
for(auto it:a1) cout<<it<<" ";
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;cin>>t;
while(t){t--;
solve();
}
}