oj.uz

Submission #67294

# Submission time Handle Problem Language Result Execution time Memory
67294 2018-08-13T19:41:30 Z yusufake DEL13 (info1cup18_del13) C++
15 / 100
 21 ms 3584 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;
 
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 < 0) assert(0);
    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:60:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     for(;t--;) bas.pb(i-A[i]+i>>1);
                       ~~~~~~^~
del13.cpp: In function 'int main()':
del13.cpp:66: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:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Integer -1 violates the range [1, 9]
2 Incorrect 4 ms 448 KB Integer -1 violates the range [1, 8]

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Integer -1 violates the range [1, 9]
2 Incorrect 4 ms 448 KB Integer -1 violates the range [1, 8]
3 Incorrect 7 ms 448 KB Integer -1 violates the range [1, 17]
4 Incorrect 7 ms 600 KB Output isn't correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 820 KB Output is correct
2 Correct 6 ms 2500 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Integer -1 violates the range [1, 9]
2 Incorrect 4 ms 448 KB Integer -1 violates the range [1, 8]
3 Incorrect 7 ms 448 KB Integer -1 violates the range [1, 17]
4 Incorrect 7 ms 600 KB Output isn't correct
5 Incorrect 3 ms 2500 KB Integer -1 violates the range [1, 75]
6 Incorrect 3 ms 2500 KB Integer -1 violates the range [1, 100]
7 Incorrect 4 ms 2500 KB Integer 95 violates the range [1, 83]

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Integer -1 violates the range [1, 9]
2 Incorrect 4 ms 448 KB Integer -1 violates the range [1, 8]
3 Incorrect 7 ms 448 KB Integer -1 violates the range [1, 17]
4 Incorrect 7 ms 600 KB Output isn't correct
5 Incorrect 3 ms 2500 KB Integer -1 violates the range [1, 75]
6 Incorrect 3 ms 2500 KB Integer -1 violates the range [1, 100]
7 Incorrect 4 ms 2500 KB Integer 95 violates the range [1, 83]
8 Incorrect 15 ms 2868 KB Integer -1 violates the range [1, 87]
9 Incorrect 16 ms 2908 KB Integer -1 violates the range [1, 84]
10 Incorrect 15 ms 2908 KB Integer 124 violates the range [1, 81]
11 Incorrect 21 ms 3584 KB Integer -1 violates the range [1, 87]