Submission #986008

#	Time	Username	Problem	Language	Result	Execution time	Memory
986008		andrei_boaca	Lamps (JOI19_lamps)	C++17	100 / 100	146 ms	71156 KiB

lamp

#include <bits/stdc++.h>

using namespace std;
vector<int> state[105];
int dp[1000005][17];
vector<int> t[2][2];
int cost[17][17];
int cnt;
string A;
string B;
int n;
int getval(vector<int> ord,int me)
{
    for(int i:ord)
    {
        if(i==0)
            me=0;
        if(i==1)
            me=1;
        if(i==2)
            me=1-me;
    }
    return me;
}
int mypoz[7];
int getcost(vector<int> a,vector<int> b)
{
    swap(a,b);
    int ans=a.size();
    for(int i=0;i<3;i++)
        mypoz[i]=-1;
    for(int i=0;i<b.size();i++)
        mypoz[b[i]]=i;
    int lg=a.size();
    for(int mask=0;mask<(1<<lg);mask++)
    {
        vector<int> sub;
        for(int i=0;i<lg;i++)
            if((mask>>i)&1)
                sub.push_back(a[i]);
        int cur=-1;
        bool ok=1;
        for(int i:sub)
        {
            if(mypoz[i]==-1||mypoz[i]<cur)
            {
                ok=0;
                break;
            }
            cur=mypoz[i];
        }
        if(ok)
            ans=min(ans,(int)a.size()-(int)sub.size());
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    cin>>A>>B;
    A="0"+A;
    B="0"+B;
    for(int mask=0;mask<(1<<3);mask++)
    {
        vector<int> me;
        for(int i=0;i<=2;i++)
            if((mask>>i)&1)
                me.push_back(i);
        do
        {
            cnt++;
            state[cnt]=me;
        }while(next_permutation(me.begin(),me.end()));
    }
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<=1;j++)
        {
            int val=getval(state[i],j);
            t[j][val].push_back(i);
        }
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
        {
            cost[i][j]=getcost(state[i],state[j]);
        }
    for(int i=1;i<=16;i++)
        dp[0][i]=2e6;
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=16;j++)
            dp[i][j]=2e6;
        for(int j:t[A[i]-'0'][B[i]-'0'])
            for(int k:t[A[i-1]-'0'][B[i-1]-'0'])
                dp[i][j]=min(dp[i][j],dp[i-1][k]+cost[k][j]);
    }
    int ans=2e6;
    for(int i=1;i<=16;i++)
        ans=min(ans,dp[n][i]);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int getcost(std::vector<int>, std::vector<int>)':
lamp.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<b.size();i++)
      |                 ~^~~~~~~~~

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