oj.uz

Submission #317185

# Submission time Handle Problem Language Result Execution time Memory
317185 2020-10-29T05:05:39 Z daniel920712 DEL13 (info1cup18_del13) C++14
0 / 100
 9 ms 512 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>

using namespace std;
int all[100005];
bool have[1000005];
vector < int > tt;
int T,N,M;
stack < int > aaa;
int F(int l,int r)
{
    int x,ok=1,i,y;
    tt.clear();
    while(!aaa.empty()) aaa.pop();
    for(i=l;i<=r;i++)
    {
        if(i==0)
        {
            if(all[i]!=1) tt.push_back(all[i]-1);
        }
        else if(all[i]-all[i-1]-1) tt.push_back(all[i]-all[i-1]-1);
    }
    if(r==M-1)
    {
        if(all[r]!=N) tt.push_back(N-all[r]);
    }
    else if(all[r+1]-all[r]-1)
    {
        tt.push_back(all[r+1]-all[r]-1);
    }
    if(tt.empty()) return 1;
    if(tt.size()==1) return 0;
    x=0;
    for(auto i:tt)
    {
        x+=i;
        if(i%2==0)
        {
            if(!aaa.empty()&&aaa.top()==0) aaa.pop();
            else aaa.push(0);
        }
        else aaa.push(1);
    }
    if(x%2==1) return 0;
    if(aaa.empty()) return 1;
    x=aaa.top();
    while(!aaa.empty())
    {
        y=aaa.top();
        aaa.pop();
    }
    if(x==0||y==0) return 0;
    return 1;
}
void Find(int here)
{
    int i;
    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++)
    {
        Find(here-(1<<tt[i-1])-(1<<tt[i+1]));
    }
}
int main()
{
    int i,j,con,xx=0,ok=0,last,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N,&M);
        if(N<=18)
        {
            if(!ok) Find(0);
            tt=(1<<N)-1;
            for(i=0;i<M;i++)
            {
                scanf("%d",&all[i]);
                tt-=(1<<all[i]);
            }
            if(have[tt]) printf("0\n");
            else printf("-1\n");
        }
        else
        {
            ok=1;
            last=0;
            for(i=0;i<M;i++) scanf("%d",&all[i]);
            if((N-M)%2) printf("-1\n");
            else
            {

                for(i=1;i<M;i++)
                {
                    if(all[i]-all[i-1]==1)
                    {
                        ok=ok&F(last,i-1);
                        last=i;
                    }
                }
                ok=ok&&F(last,M-1);
                printf("%d\n",ok-1);
            }
        }


    }

    return 0;
}

Compilation message

del13.cpp: In function 'int F(int, int)':
del13.cpp:17:11: warning: unused variable 'ok' [-Wunused-variable]
   17 |     int x,ok=1,i,y;
      |           ^~
del13.cpp: In function 'void Find(int)':
del13.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(i=1;i<tt.size()-1;i++)
      |             ~^~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:77:11: warning: unused variable 'j' [-Wunused-variable]
   77 |     int i,j,con,xx=0,ok=0,last,tt=0;
      |           ^
del13.cpp:77:13: warning: unused variable 'con' [-Wunused-variable]
   77 |     int i,j,con,xx=0,ok=0,last,tt=0;
      |             ^~~
del13.cpp:77:17: warning: unused variable 'xx' [-Wunused-variable]
   77 |     int i,j,con,xx=0,ok=0,last,tt=0;
      |                 ^~
del13.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
del13.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%d %d",&N,&M);
      |         ~~~~~^~~~~~~~~~~~~~~
del13.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |                 scanf("%d",&all[i]);
      |                 ~~~~~^~~~~~~~~~~~~~
del13.cpp:98:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |             for(i=0;i<M;i++) scanf("%d",&all[i]);
      |                              ~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 8 ms 384 KB Output isn't correct
9 Incorrect 9 ms 384 KB Output isn't correct
10 Incorrect 8 ms 384 KB Output isn't correct
11 Incorrect 8 ms 512 KB Output isn't correct