Submission #988754

#	Time	Username	Problem	Language	Result	Execution time	Memory
988754		racsosabe	Board (CEOI13_board)	C++14	100 / 100	3 ms	1120 KiB

board

// 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 (stderr)

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 / 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