Submission #376192

#	Time	Username	Problem	Language	Result	Execution time	Memory
376192		daniel920712	Lamps (JOI19_lamps)	C++14	4 / 100	260 ms	129772 KiB

lamp

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <time.h>

using namespace std;
char a[1000005];
char b[1000005];
bool have[15][1000005]={0};
int DP[15][1000005],N;
bool vis[1000005]={0};
int Father[1000005];
queue < pair < int , int > > BFS;
int F(int what,int here)
{
    if(here==N) return 0;
    if(have[what][here]) return DP[what][here];
    DP[what][here]=2e9;
    have[what][here]=1;
    if(a[here]==b[here]) DP[what][here]=min(DP[what][here],F(0,here+1));
    if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1)+1);
    if(b[here]=='1')
    {
        DP[what][here]=min(DP[what][here],F(3,here+1)+2);
        DP[what][here]=min(DP[what][here],F(5,here+1)+1);
        DP[what][here]=min(DP[what][here],F(6,here+1)+2);
        DP[what][here]=min(DP[what][here],F(9,here+1)+2);
    }
    else
    {
        DP[what][here]=min(DP[what][here],F(2,here+1)+2);
        DP[what][here]=min(DP[what][here],F(4,here+1)+1);
        DP[what][here]=min(DP[what][here],F(7,here+1)+2);
        DP[what][here]=min(DP[what][here],F(8,here+1)+2);
    }
    if(what==1)
    {
        if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        else
        {
            if(b[here]=='1')
            {
                DP[what][here]=min(DP[what][here],F(6,here+1)+1);
                DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            }
            else
            {
                DP[what][here]=min(DP[what][here],F(7,here+1)+1);
                DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            }
        }
    }
    if(what==2)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(5,here+1));
            DP[what][here]=min(DP[what][here],F(6,here+1)+1);
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(2,here+1));
    }
    if(what==3)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(4,here+1));
            DP[what][here]=min(DP[what][here],F(7,here+1)+1);
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(3,here+1));
    }
    if(what==4)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(4,here+1));
    }
    if(what==5)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(5,here+1));
    }
    if(what==6)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(6,here+1));
    }
    if(what==7)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(7,here+1));
    }
    if(what==8)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            DP[what][here]=min(DP[what][here],F(5,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(8,here+1));
    }
    if(what==9)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            DP[what][here]=min(DP[what][here],F(4,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(9,here+1));
    }
    return DP[what][here];
}
int main()
{
    int M,ans=0,i,j,x=0,y=0,aa,tt,st;
    scanf("%d",&N);
    scanf("%s %s",a,b);
    /*srand(time(NULL));
    //N=15;
    x=y=0;
    for(i=0;i<N;i++)
    {
        //a[i]=rand()%2+'0';
        //b[i]=rand()%2+'0';
        x*=2;
        x+=a[i]-'0';
        y*=2;
        y+=b[i]-'0';
    }
    st=x;
    printf("%s\n%s\n",a,b);

    BFS.push(make_pair(x,0));
    while(!BFS.empty())
    {
        x=BFS.front().first;
        aa=BFS.front().second;
        BFS.pop();
        //if(vis[x]) continue;
        vis[x]=1;
        //printf("%d %d %d\n",x,y,aa);
        if(x==y)
        {
            printf("%d %d\n",aa,F(0,0));
            while(y!=st)
            {
                for(i=N-1;i>=0;i--)
                {
                    if(y&(1<<i)) printf("1");
                    else printf("0");
                }
                printf("\n");
                y=Father[y];
            }
            for(i=N-1;i>=0;i--)
            {
                if(y&(1<<i)) printf("1");
                else printf("0");
            }
            printf("\n");

            if(F(0,0)>aa) while(1);

            return 0;
        }
        tt=0;
        for(i=0;i<N;i++)
        {
            tt=x;
            for(j=i;j<N;j++)
            {
                if(tt&(1<<j)) tt-=1<<j;
                //printf("vv %d %d\n",tt,vis[tt]);
                if(!vis[tt])
                {
                    vis[tt]=1;
                    Father[tt]=x;
                    BFS.push(make_pair(tt,aa+1));
                }
            }
        }

        for(i=0;i<N;i++)
        {
            tt=x;
            for(j=i;j<N;j++)
            {
                if(!(tt&(1<<j))) tt+=1<<j;
                if(!vis[tt])
                {
                    vis[tt]=1;
                    Father[tt]=x;
                    BFS.push(make_pair(tt,aa+1));
                }
            }
        }

        for(i=0;i<N;i++)
        {
            tt=x;
            for(j=i;j<N;j++)
            {
                if(!(tt&(1<<j))) tt+=1<<j;
                else tt-=1<<j;
                if(!vis[tt])
                {
                    vis[tt]=1;
                    Father[tt]=x;
                    BFS.push(make_pair(tt,aa+1));
                }
            }
        }


    }
    //printf("%d\n",F(0));*/
    printf("%d\n",F(0,0));
    return 0;
}
/*
15
011011010101111
101111100001011
*/

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:136:9: warning: unused variable 'M' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |         ^
lamp.cpp:136:11: warning: unused variable 'ans' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |           ^~~
lamp.cpp:136:17: warning: unused variable 'i' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                 ^
lamp.cpp:136:19: warning: unused variable 'j' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                   ^
lamp.cpp:136:21: warning: unused variable 'x' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                     ^
lamp.cpp:136:25: warning: unused variable 'y' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                         ^
lamp.cpp:136:29: warning: unused variable 'aa' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                             ^~
lamp.cpp:136:32: warning: unused variable 'tt' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                                ^~
lamp.cpp:136:35: warning: unused variable 'st' [-Wunused-variable]
  136 |     int M,ans=0,i,j,x=0,y=0,aa,tt,st;
      |                                   ^~
lamp.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
lamp.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     scanf("%s %s",a,b);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49