제출 #233640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233640		Coroian_David	Lamps (JOI19_lamps)	C++11	100 / 100	422 ms	90588 KiB

lamp

#include <bits/stdc++.h>

#define MAX_N 1000000

using namespace std;

const int sqrInf = (1e9) - 1;

int n;

string a, b;

int rez;
int dp[MAX_N + 1][16];

void readFile()
{
    cin >> n;
    cin >> a >> b;

    a = " " + a;
    b = " " + b;

    for(int i = 1; i <= n; i ++)
    {
        a[i] -= '0';
        b[i] -= '0';
    }
}

int p[4][2];

///ON OFF T

vector <int> g[MAX_N + 1];

void add(int a, int b)
{
    g[a].push_back(b);
}

struct elem
{
    int a, b, c;

    bool operator == (elem &x)
    {
        return (a == x.a && b == x.b && c == x.c);
    }
};

elem f[16];

int cod[16];
int r[16][2];

void preCalc()
{
    p[1][0] = p[1][1] = 1;
    p[2][0] = p[2][1] = 0;
    p[3][1] = 0;
    p[3][0] = 1;

    cod[0] = 0;///000
    cod[1] = 1;///001
    cod[2] = 2;///010
    cod[3] = 4;///100

    cod[4] = cod[5] = 3;///011
    cod[6] = cod[7] = 5;///101
    cod[8] = cod[9] = 6;///110

    cod[10] = cod[11] = cod[12] = cod[13] = cod[14] = cod[15] = 7;///111

    r[0][0] = 0;
    r[0][1] = 1;

    r[1][0] = r[1][1] = 1;
    r[2][0] = r[2][1] = 0;

    r[3][1] = 0;
    r[3][0] = 1;

    r[4][0] = r[4][1] = 0;
    r[5][0] = r[5][1] = 1;
    r[6][0] = r[6][1] = 0;
    r[7][0] = r[7][1] = 1;
    r[8][0] = r[8][1] = 1;
    r[9][0] = r[9][1] = 0;

    r[10][0] = r[10][1] = 1;
    r[11][0] = r[11][1] = 0;
    r[12][0] = r[12][1] = 0;
    r[13][0] = r[13][1] = 1;
    r[14][0] = r[14][1] = 0;
    r[15][0] = r[15][1] = 1;

    for(int i = 1; i <= 15; i ++)
        add(i, 0);

    for(int i = 4; i <= 7; i ++)
        add(i, 1);

    add(4, 2);
    add(5, 2);
    add(8, 2);
    add(9, 2);

    for(int i = 6; i <= 9; i ++)
        add(i, 3);

    for(int i = 10; i <= 15; i ++)
    {
        add(i, 1);
        add(i, 2);
        add(i, 3);
    }

    add(10, 4);
    add(10, 6);
    add(10, 8);

    add(11, 4);
    add(11, 9);
    add(11, 6);

    add(12, 6);
    add(12, 8);
    add(12, 5);

    add(13, 7);
    add(13, 5);
    add(13, 8);

    add(14, 4);
    add(14, 9);
    add(14, 7);

    add(15, 5);
    add(15, 7);
    add(15, 9);

    f[0] = {0, 0, 0};
    f[1] = {1, 0, 0};
    f[2] = {2, 0, 0};
    f[3] = {3, 0, 0};
    f[4] = {1, 2, 0};
    f[5] = {2, 1, 0};
    f[6] = {1, 3, 0};
    f[7] = {3, 1, 0};
    f[8] = {2, 3, 0};
    f[9] = {3, 2, 0};
    f[10] = {1, 2, 3};
    f[11] = {1, 3, 2};
    f[12] = {2, 1, 3};
    f[13] = {2, 3, 1};
    f[14] = {3, 1, 2};
    f[15] = {3, 2, 1};
}

int cost[16][16];

int Cost(int a, int b)
{
    int c = 0;
    for(int x = 0; x <= 2; x ++)
    {
        if((((1 << x) & cod[a]) == 0) && (((1 << x) & cod[b]) != 0))
            c ++;
    }

    return c;
}

int viz[16];
int que[16];

int getCod(elem x)
{
    for(int i = 0; i <= 15; i ++)
    {
        if(f[i] == x)
            return i;
    }

    return -1;
}

int bagaSt(elem &x, int i)
{
    x.c = x.b;
    x.b = x.a;
    x.a = i;

    return getCod(x);
}

int bagaDr(elem &x, int i)
{
    if(x.a == 0)
        x.a = i;

    else if(x.b == 0)
        x.b = i;

    else
        x.c = i;

    return getCod(x);
}

int bagaMid(elem &x, int i)
{
    x.c = x.b;
    x.b = i;

    return getCod(x);
}

void bfs(int s)
{
    memset(viz, 0, sizeof(viz));
    int st = 1, dr = 0;

    for(auto u : g[s])
    {
        que[++ dr] = u;
        viz[u] = 1;
    }

    que[++ dr] = s;
    viz[s] = 1;

    int c = 0;

    while(st <= dr)
    {
        int cr = que[st ++];

        if(cr <= 10)
        for(int i = 1; i <= 3; i ++)
        {
            elem x = f[cr];
            c = bagaSt(x, i);
            if(c != -1 && viz[c] == 0)
            {
                cost[s][c] = cost[s][cr] + 1;
                viz[c] = 1;
                que[++ dr] = c;
            }

            x = f[cr];
            c = bagaDr(x, i);
            if(c != -1 && viz[c] == 0)
            {
                cost[s][c] = cost[s][cr] + 1;
                viz[c] = 1;
                que[++ dr] = c;
            }

            if(cr >= 4 && cr <= 9)
            {
                x = f[cr];
                c = bagaMid(x, i);
                if(c != -1 && viz[c] == 0)
                {
                    cost[s][c] = cost[s][cr] + 1;
                    viz[c] = 1;
                    que[++ dr] = c;
                }
            }
        }
    }
}

void getCosts()
{
    for(int j = 0; j <= 15; j ++)
    {
        cost[0][j] = Cost(0, j);
        cost[j][0] = 0;

        //cout << "LA " << j << " " << cost[0][j] << "\n";
    }

    for(int i = 1; i <= 15; i ++)
    {
        bfs(i);

       // for(int j = 1; j <= 15; j ++)
          //  cout << " DE LA " << i << " La " << j << " " << cost[i][j] << "\n";
    }
}

void getDp()
{
    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0; j <= 15; j ++)
            dp[i][j] = sqrInf;
    }

    dp[0][0] = 0;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j <= 15; j ++)
        {
            if(dp[i][j] != sqrInf)
            {
                //cout << " SUJNTEMN " << i << " COD " << j << "  DP " << dp[i][j] << "\n";

                for(int h = 0; h <= 15; h ++)
                {
                    if(r[h][a[i + 1]] == b[i + 1])
                    {
                       // cout << "MERGEM urm " << h << " cost " << cost[j][h] << "\n";

                        dp[i + 1][h] = min(dp[i + 1][h], dp[i][j] + cost[j][h]);
                    }
                }
            }
        }
    }

   // cout << (int)a[n] << " " << (int)b[n] << " " << r[0][0] << "\n";

    rez = sqrInf;
    for(int i = 0; i <= 15; i ++)
    {
        if(r[i][a[n]] == b[n])
            rez = min(rez, dp[n][i]);
    }
}

void solve()
{
    preCalc();

    getCosts();

    getDp();
}

void printFile()
{
    cout << rez << "\n";
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'void getDp()':
lamp.cpp:315:37: warning: array subscript has type 'char' [-Wchar-subscripts]
                     if(r[h][a[i + 1]] == b[i + 1])
                                     ^
lamp.cpp:331:21: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(r[i][a[n]] == b[n])
                     ^

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