oj.uz

Submission #480903

# Submission time Handle Problem Language Result Execution time Memory
480903 2021-10-18T15:58:12 Z blue Board (CEOI13_board) C++17
10 / 100
 200 ms 1268 KB 
#include <iostream>
#include <vector>
#include <string>
#include <deque>
using namespace std;

const int MX = 100'000; //FIX

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<int> mov[2];
    vector<int> depth(2, 0);

    for(int q = 0; q < 2; q++)
    {
        string A;
        cin >> A;

        mov[q] = vector<int>(1+MX, 0);

        for(char c: A)
        {
            if(c == '1') depth[q]++;
            else if(c == '2')
            {
                depth[q]++;
                mov[q][depth[q]]++;
            }
            else if(c == 'U') depth[q]--;
            else if(c == 'L') mov[q][depth[q]]--;
            else if(c == 'R') mov[q][depth[q]]++;
        }

        for(int d = MX; d >= 1; d--)
        {
            // cerr << d << ' ' << mov[q][d] << '\n';
            mov[q][d-1] += mov[q][d]/2;
            mov[q][d] -= 2*(mov[q][d]/2);
            if(mov[q][d] == -1)
            {
                mov[q][d-1]--;
                mov[q][d] += 2;
            }
        }
    }

    int X = 0;
    int Y = 1;
    if(depth[X] > depth[Y]) swap(X, Y);

    int basicAns = depth[Y] - depth[X];

    depth[Y] = depth[X];

    int D = depth[X];

    int ans = 1'000'000;

    // for(int f = 1; f <= D; f++) cerr << mov[0][f] << ' ' << mov[1][f] << '\n';


    for(; D >= 0; D--)
    {
        int v1 = 1;
        int v2 = 1;
        for(int d = 1; d <= D; d++)
        {
            v1 = 2*v1 + mov[0][d];
            v2 = 2*v2 + mov[1][d];
        }

        // cerr << "v = " << v1 << ' ' << v2 << '\n';

        // cerr << D << ' ' << 2*(depth[X] - D) + abs(v1 - v2) << '\n';

        ans = min(ans, 2*(depth[X] - D) + abs(v1 - v2));
    }

    cout << basicAns + ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Incorrect 2 ms 1100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 924 ms 1240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 904 ms 1264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 896 ms 1268 KB Time limit exceeded
2 Halted 0 ms 0 KB -