oj.uz

답안 #67282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67282 2018-08-13T19:19:26 Z yusufake DEL13 (info1cup18_del13) C++
15 / 100
 14 ms 2736 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&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);
         ~~~~~^~~~~~~~~

Subtask #1
0.0 / 15.0

# 결과 실행 시간 메모리 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 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 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 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1036 KB Output is correct
2 Correct 7 ms 2736 KB Output is correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 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 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 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 628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 2736 KB Execution killed with signal 11 (could be triggered by violating memory limits)