Submission #821926

#	Time	Username	Problem	Language	Result	Execution time	Memory
821926		BidoTeima	Lamps (JOI19_lamps)	C++17	6 / 100	1076 ms	65284 KiB

lamp

#include <bits/stdc++.h>
typedef long long ll;
using namespace std; 

int main()
{        
    int n;
    string a,b;
    cin>>n>>a>>b;
    for(char&ch:a)ch-='0';
    for(char&ch:b)ch-='0';
    map<vector<int>,int>ind{};
    vector<int>vec[20]; 
    vector<int>vmsk[20];
    int mask[20];
    int to[2][20];
    int cur=0;
    for(int i = 0; i < 8; i++){
        vector<int>v;
        int msk=0;
        for(int j = 0; j < 3; j++){
            if(i&(1<<j))v.push_back(j),msk+=(1<<j);
        }
        vmsk[msk]=v;
        do{
            vec[cur]=v;
            ind[v]=cur;
            mask[cur]=msk;
            ++cur;
        }while(next_permutation(v.begin(),v.end()));
    }
    int dp[cur][n+1];
    for(int i = 0; i < cur; i++){
        for(int j = 0; j < n + 1; j++){
            dp[i][j]=1e6+1;
        }
    }
    for(int i = 0; i < cur; i++){ 
        int val = a[0];
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        if(val==b[0]){
            dp[i][0]=vec[i].size();
            //assert(vec[i].size());
        }
        to[a[0]][i]=val;
        val=a[0]^1;
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        to[a[0]^1][i]=val;
    }
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < cur; j++){
            assert(dp[j][i]);
        }
    }*/
    for(int i = 0; i + 1 < n; i++){
        for(int j = 0; j < cur; j++){
            if(dp[j][i]>n)continue;
            vector<int>v=vec[j];
            for(int rmv=0;rmv<8;rmv++){
                if((rmv & mask[j]) != rmv){
                    continue;
                } 
                for(int add = 0; add < 8; add++){
                    if((add & (mask[j]-rmv) ) != 0){
                        continue;
                    } 
                    vector<int>v2=vmsk[add];
                    do{
                        vector<int>v3;
                        for(int x:v)if(!(rmv&(1<<x)))v3.push_back(x);
                        for(int x:v2)v3.push_back(x);
                        int&x=ind[v3];
                        if(to[a[i+1]][x]==b[i+1]){
                            //cout<<dp[cur][i]<<"transfers to"<<dp[x][i+1]<<"cuz of this crap: ";
                            //bool bruh = dp[x][i+1]>0;
                            dp[x][i+1]=min(dp[x][i+1],dp[j][i]+__builtin_popcount(add));
                            /*if(bruh && dp[x][i+1]==0)cout<<"*****GOTCHA U LIL PIECE OF RUBBISH";
                            for(int x:v)cout<<x<<' ';
                            cout<<"rmv:";
                            for(int x = 0; x < 3; x++)if(rmv&(1<<x))cout<<x<<' ';
                            cout<<"add:";
                            for(int x:v2)cout<<x<<' ';
                            cout<<"cur: ";
                            cout<<int(a[i+1]);
                            cout<<"reached: ";
                            cout<<int(b[i+1]);
                            cout<<"vthree:";
                            for(int x:v3)cout<<x<<' ';
                            cout<<'\n';*/
                        }
                    }while(next_permutation(v2.begin(),v2.end()));
                }
            }
        }
    }
    int ans = 1e9;
    for(int j = 0; j < cur; j++){
        ans=min(ans,dp[j][n-1]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:49:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |         to[a[0]][i]=val;
      |                ^
lamp.cpp:81:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |                         if(to[a[i+1]][x]==b[i+1]){
      |                                     ^

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