oj.uz

Submission #988754

# Submission time Handle Problem Language Result Execution time Memory
988754 2024-05-25T23:36:42 Z racsosabe Board (CEOI13_board) C++14
100 / 100
 3 ms 1120 KB 
// CEOI 2013 - Task: Board - Solution
// Author: Gustav Matula

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>

using namespace std;

#define MAX 100005

char pa[MAX]; int _a[MAX], loga, *a;
char pb[MAX]; int _b[MAX], logb, *b;

void carry(int *idx, int i) {
  idx[i - 1] += idx[i] / 2 - (idx[i] % 2 == -1);
  idx[i] = abs(idx[i]) % 2;
}

void trace(char *path, int *idx, int &log) {
  int n = strlen(path);
  idx[0] = log = 1;

  for (int i = 0; i < n; ++i) {
    if (path[i] == '1') idx[log++] = 0;
    if (path[i] == '2') idx[log++] = 1;
    if (path[i] == 'L') --idx[log - 1];
    if (path[i] == 'R') ++idx[log - 1];
    if (path[i] == 'U') carry(idx, --log);
  }

  for (int i = log - 1; i >= 1; --i) carry(idx, i);

  int r = 0; while (idx[r] == 0) ++r;
  for (int i = r; i < log; ++i) idx[i - r] = idx[i];
  log -= r;
}

int main(void)
{
  scanf("%s", pa); trace(pa, a = _a, loga);
  scanf("%s", pb); trace(pb, b = _b, logb);

  int log = min(loga, logb);
  int sol = 1 << 20;
  int delta = 0;

  for (int i = 0; i < log && delta < (1 << 20); ++i) {
    delta = delta * 2 + a[i] - b[i];
    sol = min(sol, abs(delta) + 2 * (log - i - 1));
  }

  printf("%d\n", sol + abs(loga - logb));

  return 0;
}

Compilation message

board.cpp:14:28: warning: built-in function 'logb' declared as non-function [-Wbuiltin-declaration-mismatch]
   14 | char pb[MAX]; int _b[MAX], logb, *b;
      |                            ^~~~
board.cpp: In function 'int main()':
board.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%s", pa); trace(pa, a = _a, loga);
      |   ~~~~~^~~~~~~~~~
board.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%s", pb); trace(pb, b = _b, logb);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 3 ms 608 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1120 KB Output is correct
2 Correct 3 ms 1112 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 480 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 948 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 1112 KB Output is correct