Submission #480884

#	Time	Username	Problem	Language	Result	Execution time	Memory
480884		blue	Board (CEOI13_board)	C++17	20 / 100	19 ms	11348 KiB

board

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    int pow2[20];
    pow2[0] = 1;
    for(int e = 1; e < 20; e++)
        pow2[e] = 2*pow2[e-1];

    vector<int> edge[25'000];

    for(int i = 2; i <= 10'000; i++)
    {
        edge[i/2].push_back(i);
        edge[i].push_back(i/2);
    }

    for(int e = 2; e < 15; e++)
    {
        for(int i = pow2[e-1]; i < pow2[e] - 1; i++)
        {
            edge[i].push_back(i+1);
            edge[i+1].push_back(i);
        }
    }

    string a, b;
    cin >> a;
    cin >> b;

    int A = 1;
    for(char c: a)
    {
        if(c == '1') A = 2*A;
        else if(c == '2') A = 2*A+1;
        else if(c == 'U') A /= 2;
        else if(c == 'L') A--;
        else A++;
    }

    int B = 1;
    for(char c: b)
    {
        if(c == '1') B = 2*B;
        else if(c == '2') B = 2*B+1;
        else if(c == 'U') B /= 2;
        else if(c == 'L') B--;
        else B++;
    }

    queue<int> tbv;
    tbv.push(A);

    vector<int> dist(1'000'000, 1'000'000);

    dist[A] = 0;

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        for(int v: edge[u])
        {
            if(dist[u] + 1 >= dist[v]) continue;
            dist[v] = dist[u] + 1;
            tbv.push(v);
        }
    }

    cout << dist[B] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10