oj.uz

Submission #67268

# Submission time Handle Problem Language Result Execution time Memory
67268 2018-08-13T18:38:23 Z yusufake DEL13 (info1cup18_del13) C++
40 / 100
 21 ms 4280 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 248 KB Output is partially correct
2 Partially correct 3 ms 364 KB Output is partially correct

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 248 KB Output is partially correct
2 Partially correct 3 ms 364 KB Output is partially correct
3 Partially correct 7 ms 448 KB Output is partially correct
4 Partially correct 9 ms 640 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 752 KB Output is partially correct
2 Partially correct 7 ms 2724 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 248 KB Output is partially correct
2 Partially correct 3 ms 364 KB Output is partially correct
3 Partially correct 7 ms 448 KB Output is partially correct
4 Partially correct 9 ms 640 KB Output is partially correct
5 Partially correct 3 ms 2724 KB Output is partially correct
6 Partially correct 3 ms 2724 KB Output is partially correct
7 Partially correct 3 ms 2724 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 248 KB Output is partially correct
2 Partially correct 3 ms 364 KB Output is partially correct
3 Partially correct 7 ms 448 KB Output is partially correct
4 Partially correct 9 ms 640 KB Output is partially correct
5 Partially correct 3 ms 2724 KB Output is partially correct
6 Partially correct 3 ms 2724 KB Output is partially correct
7 Partially correct 3 ms 2724 KB Output is partially correct
8 Partially correct 12 ms 3400 KB Output is partially correct
9 Partially correct 16 ms 3716 KB Output is partially correct
10 Partially correct 17 ms 3884 KB Output is partially correct
11 Partially correct 21 ms 4280 KB Output is partially correct