#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
vector < int > bas,son;
int M[N][3],A[N],P[N],H[N],n,q,x,i,j,k,t,p,ww,ok;
int f(int i, int h){
if(i == 0) return h==0;
int &r = M[i][h];
if(r != -1) return r;
r = 0;
if(h > A[i]) return r = 0;
if(h == 0){
if(A[i]&1) r = f(P[i],1);
else r = f(P[i],2);
}
if(h == 1){
if(A[i]&1) { r = f(P[i],0); if(A[i]>2) r |= f(P[i],2); }
else r = f(P[i],1);
}
if(h == 2){
if(A[i]&1) r = f(P[i],1);
else { r = f(P[i],0); if(A[i]>3) r |= f(P[i],2); }
}
return r;
}
void g(int i, int h){
if(i == 0) return;
for(int j=0;j<h;j++) son.pb(i);
int x = 0;
if(h == 0){
if(A[i]&1) g(P[i],x=1);
else g(P[i],x=2);
}
if(h == 1){
if(A[i]&1) { if(f(P[i],0))f(P[i],x=0); else g(P[i],x=2); }
else g(P[i],x=1);
}
if(h == 2){
if(A[i]&1) g(P[i],x=1);
else { if(f(P[i],0)) g(P[i],x=0); else g(P[i],x=2); }
}
int t = A[i] - h - x;
if(t&1) assert(0);
t>>=1;
for(;t--;) bas.pb(i-A[i]+i>>1);
}
int main (){
cin >> ww; for(;ww--; puts("")){
scanf ("%d%d",&n,&q);
for(i=0;i<=n+1;i++) {
M[i][0] = M[i][1] = M[i][2] = -1; H[i]=0;
P[i]=0; A[i]=0;
}
H[0] = H[n+1] = 1;
for(i=1;i<=q;i++){
scanf("%d",&x);
H[x] = 1;
}
ok = 1;
bas.clear(); son.clear();
for (p=0,i=1; i<=n; i=j){
if(H[i]) { j=i+1; continue; }
for(j=i; !H[j] && j<=n; j++);
//cout << i << " " << j << " qq\n";
P[j] = p; A[j] = j-i; p = j;
//if(!H[j]) assert(0);
if(j == n+1 || H[j+1]){
ok &= f(j,0);
if(ok) g(j,0);
p = 0;
}
}
if(ok==0){
printf("-1");
continue;
}
printf("%d\n", (n-q)/2);
//cout << son.size() << " im\n";
if((int)bas.size() + (int)son.size() != (n-q)/2) assert(0);
for(auto x : bas) printf("%d ", x);
//return 0;
for(auto x : son) printf("%d ", x);
//return 0;
}
}
Compilation message
del13.cpp: In function 'void g(int, int)':
del13.cpp:59:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
for(;t--;) bas.pb(i-A[i]+i>>1);
~~~~~~^~
del13.cpp: In function 'int main()':
del13.cpp:65:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d",&n,&q);
~~~~~~^~~~~~~~~~~~~~
del13.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1000 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
4 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
3 ms |
692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
2 ms |
844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
4 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
3 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
2 ms |
2724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
