oj.uz

Submission #67296

# Submission time Handle Problem Language Result Execution time Memory
67296 2018-08-13T19:43:28 Z yusufake DEL13 (info1cup18_del13) C++
100 / 100
 24 ms 3656 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))g(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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 3 ms 484 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 11 ms 484 KB Output is correct
4 Correct 9 ms 572 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 712 KB Output is correct
2 Correct 7 ms 2392 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 11 ms 484 KB Output is correct
4 Correct 9 ms 572 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 4 ms 2392 KB Output is correct
7 Correct 4 ms 2392 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 11 ms 484 KB Output is correct
4 Correct 9 ms 572 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 4 ms 2392 KB Output is correct
7 Correct 4 ms 2392 KB Output is correct
8 Correct 18 ms 2956 KB Output is correct
9 Correct 17 ms 2956 KB Output is correct
10 Correct 24 ms 2956 KB Output is correct
11 Correct 23 ms 3656 KB Output is correct