oj.uz

Submission #105468

# Submission time Handle Problem Language Result Execution time Memory
105468 2019-04-12T12:52:44 Z alexpetrescu Board (CEOI13_board) C++14
70 / 100
 200 ms 1116 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')
        n--;
    else if (s[poz] == 'L') {
        int p = n - 1;
        while (v[p] == 0) {
            v[p] = 1;
            p--;
        }
        v[p] = 0;
    } else {
        int p = n - 1;
        while (v[p] == 1) {
            v[p] = 0;
            p--;
        }
        v[p] = 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);
}

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:40: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 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 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 512 KB Output is correct
3 Correct 4 ms 512 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 2 ms 384 KB Output is correct
2 Correct 7 ms 560 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1116 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 1048 ms 1016 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 1068 ms 1064 KB Time limit exceeded
2 Halted 0 ms 0 KB -