oj.uz

Submission #62431

# Submission time Handle Problem Language Result Execution time Memory
62431 2018-07-28T12:52:47 Z Nnandi Board (CEOI13_board) C++14
100 / 100
 7 ms 3868 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: 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]
   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]
   scanf("%s", pb); trace(pb, b = _b, logb);
   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 860 KB Output is correct
2 Correct 7 ms 1220 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2668 KB Output is correct
2 Correct 7 ms 2888 KB Output is correct
3 Correct 2 ms 2888 KB Output is correct
4 Correct 4 ms 2888 KB Output is correct
5 Correct 7 ms 3188 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3308 KB Output is correct
2 Correct 7 ms 3452 KB Output is correct
3 Correct 5 ms 3524 KB Output is correct
4 Correct 4 ms 3524 KB Output is correct
5 Correct 4 ms 3524 KB Output is correct
6 Correct 6 ms 3868 KB Output is correct