Submission #1291110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291110		simona1230	Lamps (JOI19_lamps)	C++20	6 / 100	202 ms	51216 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

int dp[1000001][10];
vector<int> v[10]={{},{1},{1,2},{1,3},{1,2,3},{1,3,2},{2},{3},{2,3},{3,2}};

int n;
string s;
int a[1000001];
int b[1000001];
int add[11][11];
string x,y;

void read()
{
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            int h=0;
            while(h<v[i].size()&&h<v[j].size()&&v[i][h]==v[j][h])
                h++;
            add[i][j]=v[j].size()-h;
        }
    }
    cin>>n>>s;
    x=s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0')a[i+1]=3;
        else a[i+1]=2;
    }

    cin>>s;
    y=s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0')b[i+1]=3;
        else b[i+1]=2;
    }

    for(int i=0;i<10;i++)
    {
        dp[1][i]=1e9;
        if(v[i].size()&&b[1]==v[i][v[i].size()-1])
            dp[1][i]=v[i].size();
    }
    if(a[1]==b[1])dp[1][0]=0;
    else dp[1][1]=1;

    for(int i=2;i<=n;i++)
    {
        if(a[i]==b[i])
        {
            dp[i][0]=1e9;
            for(int j=0;j<10;j++)
                dp[i][0]=min(dp[i][0],dp[i-1][j]);
            dp[i][1]=1e9;
        }
        else
        {
            dp[i][1]=1e9;
            for(int j1=0;j1<10;j1++)
                dp[i][1]=min(dp[i-1][j1]+add[j1][1],dp[i][1]);
            dp[i][0]=1e9;
        }

        for(int j=2;j<10;j++)
        {
            if(b[i]!=v[j][v[j].size()-1])
            {
                dp[i][j]=1e9;
                continue;
            }

            dp[i][j]=1e9;
            for(int j1=0;j1<10;j1++)
            {
                dp[i][j]=min(dp[i-1][j1]+add[j1][j],dp[i][j]);
            }
        }

        /*for(int j=0;j<10;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;*/
    }

    int ans=n;
    for(int i=0;i<10;i++)
        ans=min(ans,dp[n][i]);
    //cout<<ans<<endl;
}

int d[1000001];

int num(string p)
{
    int ans=0;
    for(int i=0;i<p.size();i++)
        if(p[i]=='1')ans+=(1<<i);
    return ans;
}


void bfs()
{
    queue<int> q;
    int xn=num(x);
    q.push(xn);
    d[xn]=1;

    while(q.size())
    {
        int c=q.front();
        q.pop();

        int t,on,of;
        for(int l=0;l<n;l++)
        {
            t=on=of=c;
            for(int r=l;r<n;r++)
            {
                if(t&(1<<r))t-=(1<<r);
                else t+=(1<<r);

                if((on&(1<<r))==0)on+=(1<<r);
                if(of&(1<<r))of-=(1<<r);

                if(d[t]==0)
                d[t]=d[c]+1,
                q.push(t);

                if(d[on]==0)
                d[on]=d[c]+1,
                q.push(on);

                if(d[of]==0)
                d[of]=d[c]+1,
                q.push(of);
            }
        }
    }

    cout<<d[num(y)]-1<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	bfs();
	return 0;
}

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