Submission #784030

#	Time	Username	Problem	Language	Result	Execution time	Memory
784030		tvladm2009	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	208 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

void solve(int n) {
  int mn = -1, mx = -1;
  int low = 1, high = n;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (query(1, mid) == n - 1) {
      mx = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  low = 1, high = mx - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (query(mid, mx) == n - 1) {
      mn = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  assert(mn != -1 && mx != -1 && mn < mx);
  vector<int> sol(n + 1, 0);
  vector<bool> used(n + 1, 0);
  sol[mn] = 1;
  sol[mx] = n;
  if (mn > 1) {
    sol[mn - 1] = query(mn - 1, mn) + 1;
  }
  for (int i = mn - 2; i >= 1; i--) {
    if (sol[i + 1] < sol[i + 2]) {
      int x = query(i, i + 2);
      if (x != sol[i + 2] - sol[i + 1]) {
        ///its less than sol[i + 1] or greater than sol[i + 2]
        int delta = sol[i + 2] - x;
        if (1 <= delta && delta <= sol[i + 1] && used[delta] == 0 && sol[i + 1] - delta == query(i, i + 1)) {
          sol[i] = delta;
          used[delta] = 1;
        } else {
          delta = sol[i + 1] + x;
          assert(sol[i + 2] <= delta && delta <= n && used[delta] == 0);
          used[delta] = 1;
          sol[i] = delta;
        }
      } else {
        int val = sol[i + 1] + query(i, i + 1);
        assert(used[val] == 0);
        used[val] = 1;
        sol[i] = val;
      }
    } else { /// sol[i + 1] > sol[i + 2]
      int x = query(i, i + 2);
      if (x != sol[i + 1] - sol[i + 2]) {
        ///its less than sol[i + 2] or greater than sol[i + 1]
        int delta = sol[i + 1] - x;
        if (delta >= sol[i + 2] && delta <= n && used[delta] == 0 && query(i, i + 1) == x) {
          used[delta] = 1;
          sol[i] = delta;
        } else {
          delta = sol[i + 2] + x;
          assert(delta <= n && delta >= sol[i + 1] && used[delta] == 0);
          used[delta] = 1;
          sol[i] = delta;
        }
      } else {
        int val = sol[i + 1] - query(i, i + 1);
        assert(used[val] == 0);
        used[val] = 1;
        sol[i] = val;
      }
    }
  }
  if (mn + 1 < mx) {
    sol[mn + 1] = sol[mn] + query(mn, mn + 1);
  }
  for (int i = mn + 2; i <= n; i++) {
    if (i == mx) {
      continue;
    }
    if (sol[i - 1] > sol[i - 2]) {
      int x = query(i - 2, i);
      cout << x << "\n";
      if (x != sol[i - 1] - sol[i - 2]) {
        ///its less than sol[i - 2] or greater than sol[i - 1]
        int delta = sol[i - 2] + x;
        if (delta <= n && delta >= sol[i - 1] && used[delta] == 0 && delta - sol[i - 1] == query(i, i - 1)) {
          sol[i] = delta;
          used[delta] = 1;
        } else {
          sol[i] = sol[i - 1] - x;
          assert(1 <= sol[i] && sol[i] < sol[i - 2] && used[sol[i]] == 0);
          used[sol[i]] = 1;
        }
      } else {
        int val = sol[i - 1] - query(i - 1, i);
        sol[i] = val;
        assert(used[val] == 0);
        used[val] = 1;
      }
    } else { /// sol[i - 2] > sol[i - 1]
      int x = query(i - 2, i);
      if (x != sol[i - 2] - sol[i - 1]) {
        ///its less than sol[i - 1] or greater than sol[i - 2]
        int delta = sol[i - 1] + x;
        if (delta <= n && delta >= sol[i - 2] && used[delta] == 0 && delta - sol[i - 1] == query(i - 1, i)) {
          sol[i] = delta;
          used[delta] = 1;
        } else {
          sol[i] = sol[i - 2] - x;
          assert(1 <= sol[i] && sol[i] < sol[i - 1] && used[sol[i]] == 0);
          used[sol[i]] = 1;
        }
      } else {
        int val = sol[i - 1] + query(i - 1, i);
        assert(used[val] == 0);
        used[val] = 1;
        sol[i] = val;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    answer(i, sol[i]);
  }
}

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