oj.uz

Submission #480884

# Submission time Handle Problem Language Result Execution time Memory
480884 2021-10-18T14:57:18 Z blue Board (CEOI13_board) C++17
20 / 100
 19 ms 11348 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 7 ms 5308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5580 KB Output is correct
2 Correct 7 ms 5452 KB Output is correct
3 Correct 10 ms 5632 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 10884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 10908 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 11348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 11316 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 11340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -