Submission #480903

#	Time	Username	Problem	Language	Result	Execution time	Memory
480903		blue	Board (CEOI13_board)	C++17	10 / 100	924 ms	1268 KiB

board

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10