oj.uz

Submission #105470

# Submission time Handle Problem Language Result Execution time Memory
105470 2019-04-12T12:56:27 Z alexpetrescu Board (CEOI13_board) C++14
100 / 100
 5 ms 1124 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 1024 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct