Submission #784223

#	Time	Username	Problem	Language	Result	Execution time	Memory
784223		tvladm2009	Xylophone (JOI18_xylophone)	C++17	0 / 100	2 ms	464 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
 
using namespace std;

/// 2 * log(N) + 2 * (N - 6) + 4

map<pair<int, int>, int> mp;
 
int ask(int l, int r) {
  if (mp.count({l, r}) > 0) {
    return mp[{l, r}];
  }
  int x = query(l, r);
  mp[{l, r}] = x;
  return x;
}
 
void solve(int n) {
  mp.clear();
  int mn = -1, mx = -1;
  int low = 1, high = n;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (ask(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 (ask(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;
  used[1] = used[n] = 1;
  if (mn > 1) {
    sol[mn - 1] = ask(mn - 1, mn) + 1;
    used[sol[mn - 1]] = 1;
  }
  for (int i = mn - 2; i >= 1; i--) {
    if (sol[i + 1] < sol[i + 2]) {
      int x = ask(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 + 1] + x;
        if (delta <= n && delta >= sol[i + 1] && used[delta] == 0) {
          sol[i] = delta;
          used[delta] = 1;
        } else {
          delta = sol[i + 2] - x;
          assert(sol[i + 1] >= delta && delta <= n && used[delta] == 0);
          used[delta] = 1;
          sol[i] = delta;
        }
      } else {
        int val = sol[i + 1] + ask(i, i + 1);
        assert(used[val] == 0);
        used[val] = 1;
        sol[i] = val;
      }
    } else { /// sol[i + 1] > sol[i + 2]
      int x = ask(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 >= 1 && delta <= sol[i + 2] && used[delta] == 0 && ask(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] - ask(i, i + 1);
        assert(used[val] == 0);
        used[val] = 1;
        sol[i] = val;
      }
    }
  }
  if (mn + 1 < mx) {
    sol[mn + 1] = sol[mn] + ask(mn, mn + 1);
    used[sol[mn + 1]] = 1;
  }
  if (mx - 1 > mn + 1) {
    sol[mx - 1] = sol[mx] - ask(mx - 1, mx);
    used[sol[mx - 1]] = 1;
  }
  if (mx + 1 <= n) {
    sol[mx + 1] = sol[mx] - ask(mx, mx + 1);
    used[sol[mx + 1]] = 1;
  }
  for (int i = mn + 2; i <= n; i++) {
    if (sol[i] != 0) {
      continue;
    }
    if (sol[i - 1] > sol[i - 2]) {
      int x = ask(i - 2, i);
      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] == ask(i - 1, i)) {
          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] - ask(i - 1, i);
        sol[i] = val;
        assert(used[val] == 0);
        used[val] = 1;
      }
    } else { /// sol[i - 2] > sol[i - 1]
      int x = ask(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] == ask(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] + ask(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