oj.uz

Submission #317945

# Submission time Handle Problem Language Result Execution time Memory
317945 2020-10-31T01:26:40 Z daniel920712 DEL13 (info1cup18_del13) C++14
100 / 100
 41 ms 4192 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>

using namespace std;
int all[100005];
int Father[1000005];
int Father2[1000005];
int xx[1000005]={0};
bool have[1000005]={0};
bool can[1000005]={0};
bool use[5][1000005]={0};
int DP[5][1000005]={0};
pair < int , int > Next[5][1000005];
vector < int > tt;
vector < int > ttt;
vector < int > ans;
set < int > temp;
int T,N,M;
stack < int > aaa;
bool F(int can,int here)
{
    if(here==M+1) return 1-can;
    if(can==1&&ttt[here]<2) return 0;
    if(ttt[here]==0)
    {
        Next[can][here]=make_pair(0,here+1);
        return F(0,here+1);
    }
    if(use[can][here]) return DP[can][here];
    DP[can][here]=0;
    if(can==1)
    {
        if(ttt[here]>=4)
        {
            if(F(1,here+1))
            {
                Next[can][here]=make_pair(1,here+1);
                DP[can][here]=1;
            }
        }
        if(F(0,here+1))
        {
            Next[can][here]=make_pair(0,here+1);
            DP[can][here]=1;
        }
    }
    else
    {
        if(F(1,here+1))
        {
            Next[can][here]=make_pair(1,here+1);
            DP[can][here]=1;
        }
    }
    if(::can[here])
    {
        if(F(0,here+1))
        {
            Next[can][here]=make_pair(0,here+1);
            DP[can][here]=1;
        }
    }
    use[can][here]=1;
    return DP[can][here];
}

void FF(int can,int here)
{
    //printf("%d %d\n",can,here);
    if(here==M+1) return;
    FF(Next[can][here].first,Next[can][here].second);
    if(Next[can][here].first) xx[here+1]+=2;
}
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]));
    }
}

int main()
{
    int i,j,con,ok=0,last,tt=0,ff=0,where;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N,&M);

        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++)
        {
            xx[i]=0;
            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]--;
                    xx[i+1]++;
                }
            }
            if(ttt[i]%2) break;

        }
        if(i!=M+1)
        {
            printf("-1\n");
            continue;
        }
        if(F(0,0)==0) printf("-1\n");
        else
        {
            FF(0,0);
            ans.clear();
            for(i=0;i<=M;i++)
            {
                temp.clear();
                for(j=all[i]+1;j<all[i+1];j++) temp.insert(j);
                N=temp.size();
                N-=xx[i];
                N-=xx[i+1];
                //printf("%d %d %d\n",all[i],all[i+1],N);
                for(j=0;j<N/2;j++)
                {
                    tt=*next(temp.begin());
                    ans.push_back(tt);
                    temp.erase(temp.upper_bound(tt));
                    temp.erase(prev(temp.lower_bound(tt)));

                }
            }
            for(i=0;i<=M;i++) while(xx[i]--) ans.push_back(all[i]);
            printf("%d\n",ans.size());
            for(auto i:ans) printf("%d ",i);
            printf("\n");


        }
        ok=1;


    }

    return 0;
}

Compilation message

del13.cpp: In function 'void Find(int)':
del13.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(i=1;i<tt.size()-1;i++)
      |             ~^~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:165:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  165 |             printf("%d\n",ans.size());
      |                     ~^    ~~~~~~~~~~
      |                      |            |
      |                      int          std::vector<int>::size_type {aka long unsigned int}
      |                     %ld
del13.cpp:101:13: warning: unused variable 'con' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |             ^~~
del13.cpp:101:17: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                 ^~
del13.cpp:101:22: warning: unused variable 'last' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                      ^~~~
del13.cpp:101:32: warning: unused variable 'ff' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                                ^~
del13.cpp:101:37: warning: unused variable 'where' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                                     ^~~~~
del13.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
del13.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         scanf("%d %d",&N,&M);
      |         ~~~~~^~~~~~~~~~~~~~~
del13.cpp:109:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |         for(i=1;i<=M;i++) scanf("%d",&all[i]);
      |                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 14 ms 896 KB Output is correct
9 Correct 14 ms 1920 KB Output is correct
10 Correct 14 ms 2048 KB Output is correct
11 Correct 41 ms 4192 KB Output is correct