Submission #67268

#	Time	Username	Problem	Language	Result	Execution time	Memory
67268		yusufake	DEL13 (info1cup18_del13)	C++98	40 / 100	21 ms	4280 KiB

del13

#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;

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;
}

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;
    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);
            p = 0;
        }
    }
    
    if(ok==0){
        printf("-1");
        continue;
    }
    printf("%d\n", (n-q)/2);
    for(i=1;i<=(n-q)/2;i++) printf("1 ");
}
}

Compilation message (stderr)

del13.cpp: In function 'int main()':
del13.cpp:41: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:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

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