Submission #1291109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291109		simona1230	Lamps (JOI19_lamps)	C++20	0 / 100	1097 ms	327680 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;
}

unordered_map<string,int> mp;

void bfs()
{
    queue<string> q;
    q.push(x);
    mp[x]=1;

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

        string t,on,of;
        for(int l=0;l<n;l++)
        {
            t=on=of=c;
            for(int r=l;r<n;r++)
            {
                if(t[r]=='1')t[r]='0';
                else t[r]='1';

                on[r]='1';
                of[r]='0';

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

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

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

    cout<<mp[y]-1<<endl;
}

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

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