Submission #763158

#	Time	Username	Problem	Language	Result	Execution time	Memory
763158		ind1v	Xylophone (JOI18_xylophone)	C++11	100 / 100	58 ms	440 KiB

xylophone

#include "xylophone.h"

const int N = 5005;

int a[N];
bool used[N];

bool in(int x, int n) {
  return 1 <= x && x <= n;
}

void solve(int n) {
  int l = 1, r = n, idx = -1;
  while (l <= r) {
    int m = l + r >> 1;
    if (query(1, m) == n - 1) {
      idx = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  a[idx] = n;
  used[n] = true;
  bool inc = true;
  for (int i = idx + 1; i <= n; i++) {
    if (i == idx + 1) {
      a[i] = n - query(idx, idx + 1);
      used[a[i]] = true;
      inc = false;
    } else {
      int d = query(i - 1, i);
      if (!in(a[i - 1] - d, n)) {
        a[i] = a[i - 1] + d;
      } else if (!in(a[i - 1] + d, n)) {
        a[i] = a[i - 1] - d;
      } else {
        if (used[a[i - 1] - d]) {
          a[i] = a[i - 1] + d;
        } else if (used[a[i - 1] + d]) {
          a[i] = a[i - 1] - d;
        } else {
          if (inc) {
            int dd = query(i - 2, i);
            if (a[i - 1] + d == a[i - 2] + dd) {
              a[i] = a[i - 1] + d;
            } else {
              a[i] = a[i - 1] - d;
            }
          } else {
            int dd = query(i - 2, i);
            if (a[i - 1] - d == a[i - 2] - dd) {
              a[i] = a[i - 1] - d;
            } else {
              a[i] = a[i - 1] + d;
            }
          }
        }
      }
      used[a[i]] = true;
      inc = a[i - 1] < a[i];
    }
  }
  for (int i = idx - 1; i >= 1; i--) {
    if (i == idx - 1) {
      a[i] = n - query(i, i + 1);
      used[a[i]] = true;
      inc = false;
    } else {
      int d = query(i, i + 1);
      if (!in(a[i + 1] - d, n)) {
        a[i] = a[i + 1] + d;
      } else if (!in(a[i + 1] + d, n)) {
        a[i] = a[i + 1] - d;
      } else {
        if (used[a[i + 1] - d]) {
          a[i] = a[i + 1] + d;
        } else if (used[a[i + 1] + d]) {
          a[i] = a[i + 1] - d;
        } else {
          if (inc) {
            int dd = query(i, i + 2);
            if (a[i + 1] + d == a[i + 2] + dd) {
              a[i] = a[i + 1] + d;
            } else {
              a[i] = a[i + 1] - d;
            }
          } else {
            int dd = query(i, i + 2);
            if (a[i + 1] - d == a[i + 2] - dd) {
              a[i] = a[i + 1] - d;
            } else {
              a[i] = a[i + 1] + d;
            }
          }
        }
      }
      used[a[i]] = true;
      inc = a[i] > a[i + 1];
    }
  }
  for(int i = 1; i <= n; i++) {
    answer(i, a[i]);
  }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int m = l + r >> 1;
      |             ~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53