oj.uz

Submission #317714

# Submission time Handle Problem Language Result Execution time Memory
317714 2020-10-30T07:43:47 Z daniel920712 DEL13 (info1cup18_del13) C++14
6 / 100
 9 ms 1764 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>

using namespace std;
int all[100005];
int Father[1000005];
int Father2[1000005];
bool have[1000005]={0};
bool can[1000005]={0};
bool use[5][1000005]={0};
int DP[5][1000005]={0};

vector < int > tt;
vector < int > ttt;
vector < int > ans;
int T,N,M;
stack < int > aaa;
bool F(int can,int here)
{
    if(here==M+1) return 1;
    if(can==1&&ttt[here]<2) return 0;
    if(ttt[here]==0) return F(0,here+1);
    if(use[can][here]) return DP[can][here];

    DP[can][here]=0;
    if(can==1)
    {
        if(ttt[here]>=4) DP[can][here]=F(1,here+1);
        DP[can][here]|=F(0,here+1);
    }
    else DP[can][here]=F(1,here+1);
    if(::can[here]) DP[can][here]|=F(0,here+1);
    use[can][here]=1;
    //printf("aa %d %d %d\n",can,here,DP[can][here]);
    return DP[can][here];
}
void Find(int here)
{
    int i;
    //printf("%d\n",here);
    if(have[here]) return;
    have[here]=1;
    vector < int > tt;
    for(i=0;i<N;i++)
    {
        if(here&(1<<i)) tt.push_back(i);
    }
    for(i=1;i<tt.size()-1;i++)
    {
        Father[here-(1<<tt[i-1])-(1<<tt[i+1])]=here;
        Father2[here-(1<<tt[i-1])-(1<<tt[i+1])]=tt[i];
        Find(here-(1<<tt[i-1])-(1<<tt[i+1]));
    }
}
void FF(int here)
{
    int i;
    if(here==(1<<N)-1) return;
    FF(Father[here]);
    ans.push_back(Father2[here]);
}
int main()
{
    int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
    //freopen("input.03","rt",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N,&M);
        //printf("%d %d %d\n",N,ff,ok);
        /*if((!ok||N==ff)&&N<=18)
        {
            //printf("aa\n");
            if(!ok)
            {
                ff=N;
                Find((1<<N)-1);
                ok=1;
            }

            tt=0;
            for(i=0;i<M;i++)
            {
                scanf("%d",&all[i]);
                all[i]--;
                tt+=(1<<all[i]);
            }
            if(have[tt])
            {
                ans.clear();
                FF(tt);
                printf("%d\n",ans.size());
                for(auto i:ans) printf("%d ",i+1);
                printf("\n");
            }
            else printf("-1\n");
        }
        else*/
        {
            ok=1;
            all[0]=0;
            for(i=1;i<=M;i++) scanf("%d",&all[i]);
            all[M+1]=N+1;
            ttt.clear();
            for(i=0;i<=M;i++)
            {
                can[i]=0;
                ttt.push_back(all[i+1]-all[i]-1);
            }

            for(i=0;i<=M;i++)
            {
                use[0][i]=0;
                use[1][i]=0;
                if(ttt[i]%2)
                {

                    if(i!=M&&ttt[i+1]>=1)
                    {
                        can[i]=1;
                        can[i+1]=1;
                        ttt[i]--;
                        ttt[i+1]--;
                    }
                }
                if(ttt[i]%2) break;

            }
            //for(i=0;i<=M;i++) printf("%d ",ttt[i]);
            //printf("\n");
            if(i!=M+1)
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n",F(0,0)-1);
            /*for(i=0;i<=M;i++)
            {
                if(ttt[i]==0) continue;
                if(!use[i]&&ttt[i]%2==0)
                {
                    if(i&&ttt[i-1]>=2)
                    {
                        use[i]=1;
                        use[i-1]=1;
                        ttt[i]-=2;
                        ttt[i-1]-=2;
                    }
                    else if(i!=M&&ttt[i+1]>=2)
                    {
                        use[i]=1;
                        use[i+1]=1;
                        ttt[i]-=2;
                        ttt[i+1]-=2;
                    }
                    //else
                }


            }

            for(i=0;i<=M;i++)
            {
                if(ttt[i]==0) continue;
                if(ttt[i]%2) ok=0;
                if(ttt[i]%2==0&&!use[i]) ok=0;
            }
            printf("%d\n",ok-1);*/



            ok=1;
        }


    }

    return 0;
}

Compilation message

del13.cpp: In function 'void Find(int)':
del13.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(i=1;i<tt.size()-1;i++)
      |             ~^~~~~~~~~~~~
del13.cpp: In function 'void FF(int)':
del13.cpp:62:9: warning: unused variable 'i' [-Wunused-variable]
   62 |     int i;
      |         ^
del13.cpp: In function 'int main()':
del13.cpp:69:11: warning: unused variable 'j' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |           ^
del13.cpp:69:13: warning: unused variable 'con' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |             ^~~
del13.cpp:69:17: warning: unused variable 'xx' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                 ^~
del13.cpp:69:22: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                      ^~
del13.cpp:69:27: warning: unused variable 'last' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                           ^~~~
del13.cpp:69:32: warning: unused variable 'tt' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                                ^~
del13.cpp:69:37: warning: unused variable 'ff' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                                     ^~
del13.cpp:69:42: warning: unused variable 'where' [-Wunused-variable]
   69 |     int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
      |                                          ^~~~~
del13.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
del13.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         scanf("%d %d",&N,&M);
      |         ~~~~~^~~~~~~~~~~~~~~
del13.cpp:107:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |             for(i=1;i<=M;i++) scanf("%d",&all[i]);
      |                               ~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Incorrect 4 ms 384 KB Output isn't correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is partially correct
2 Correct 2 ms 416 KB Output is partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is partially correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Correct 1 ms 384 KB Output is partially correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is partially correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Correct 1 ms 384 KB Output is partially correct
8 Correct 7 ms 512 KB Output is partially correct
9 Correct 8 ms 896 KB Output is partially correct
10 Correct 7 ms 1024 KB Output is partially correct
11 Correct 9 ms 1764 KB Output is partially correct