Submission #105470

#	Time	Username	Problem	Language	Result	Execution time	Memory
105470		alexpetrescu	Board (CEOI13_board)	C++14	100 / 100	5 ms	1124 KiB

board

#include <cstdio>
#include <cstdlib>
#include <algorithm>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define MAXN 100000
char s[MAXN + 10];
int n[2], a[2][MAXN];

inline void un_pas(int &poz, int &n, int v[]) {
    if (s[poz] == '1')
        v[n++] = 0;
    else if (s[poz] == '2')
        v[n++] = 1;
    else if (s[poz] == 'U') {
        if (n > 1) {
            if (v[n - 1] > 0)
                v[n - 2] += v[n - 1] / 2;
            else
                v[n - 2] -= (-v[n - 1] + 1) / 2;
        }
        n--;
    } else if (s[poz] == 'R')
        v[n - 1]++;
    else
        v[n - 1]--;
    poz++;
}

inline void getVal(int &n, int v[]) {
    fgets(s, MAXN + 5, fin);
    int poz = 0;
    while (s[poz] != '\n')
        un_pas(poz, n, v);
    for (int i = n - 1; i > 0; i--) {
        if (v[i] > 0) {
            v[i - 1] += v[i] / 2;
            v[i] %= 2;
        } else {
            v[i] = -v[i];
            v[i - 1] -= (1 + v[i]) / 2;
            v[i] %= 2;
        }
    }
    if (v[0] != bool(v[0]))
        exit(1);
}

int main() {
    getVal(n[0], a[0]);
    getVal(n[1], a[1]);

    int x = 0, y = 1;
    if (n[x] > n[y])
        std::swap(x, y);
    int dist = n[y] - n[x];
    n[y] = n[x];
    int poz = 0;
    while (poz < n[x] && a[0][poz] == a[1][poz])
        poz++;

    if (poz < n[x] && a[x][poz] == 1)
        std::swap(x, y);

    dist += 2 * (n[x] - poz);
    int m = 0, ans = dist;
    for (int i = poz; m < 1000000000 && i < n[x]; i++) {
        dist -= 2;
        m *= 2;
        if (a[x][i] == 1 && a[y][i] == 0)
            m--;
        else if (a[x][i] == 0 && a[y][i] == 1)
            m++;
        ans = std::min(ans, dist + m);
    }

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

board.cpp: In function 'void getVal(int&, int*)':
board.cpp:34:10: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(s, MAXN + 5, fin);
     ~~~~~^~~~~~~~~~~~~~~~~~

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