제출 #653315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653315		Dec0Dedd	Xylophone (JOI18_xylophone)	C++14	100 / 100	76 ms	428 KiB

xylophone

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

using namespace std;

const int N = 5e3+1;

int ans[N], n;
bool us[N];

// [i, j, k]
int que(int l, int r) {
   return query(min(l, r), max(l, r));
}

int val(int i, int j, int k, int l) {
   int p=que(k, i), res=0;

   int y=ans[k], a=ans[j];
   assert(y != a+l), assert(y != a-l);
   if (y > a+l) {
      if (p == y-a) res=a+l;
      else res=a-l;
   } else if (y > a && y < a+l) {
      if (p == l) res=a+l;
      else res=a-l;
   } else if (y < a && y > a-l) {
      if (p == l) res=a-l;
      else res=a+l;
   } else if (y < a-l) {
      if (p == a-y) res=a-l;
      else res=a+l;
   }

   assert(1 <= res && res <= n);
   assert(!us[res]);
   return res;
}

void solve(int np) {
   n=np;
   int l=1, r=n, x=1;
   while (l <= r) {
      int m=(l+r)/2;
      if (que(1, m) == n-1) r=m-1, x=m;
      else l=m+1;
   } ans[x]=n;


   if (x < n) ans[x+1]=n-que(x, x+1), us[ans[x+1]]=true;
   if (x > 1) ans[x-1]=n-que(x-1, x), us[ans[x-1]]=true;

   us[n]=true;
   for (int i=x+2; i<=n; ++i) {
      int l=que(i-1, i);

      if (ans[i-1]+l > n || us[ans[i-1]+l]) ans[i]=ans[i-1]-l;
      else if (ans[i-1]-l < 1 || us[ans[i-1]-l]) ans[i]=ans[i-1]+l;
      else ans[i]=val(i, i-1, i-2, l);
      us[ans[i]]=true;
   }

   for (int i=x-2; i>=1; --i) {
      int l=que(i, i+1);
      if (ans[i+1]+l > n || us[ans[i+1]+l]) ans[i]=ans[i+1]-l;
      else if (ans[i+1]-l < 1 || us[ans[i+1]-l]) ans[i]=ans[i+1]+l;
      else ans[i]=val(i, i+1, i+2, l);
      us[ans[i]]=true;
   }

   for (int i=1; i<=n; ++i) {
      assert(ans[i] > 0);
      answer(i, ans[i]);
   }
}

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