제출 #653309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653309		Dec0Dedd	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	208 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=que(i, j), res=0;

   if (ans[j]+l > n || us[ans[j]+l]) res=ans[j]-l;
   else if (ans[j]-l < 1 || us[ans[j]-l]) res=ans[j]+l;
   else {
      int p=query(k, i);

      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;
      }
   }

   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-query(x, x+1);
   if (x > 1) ans[x-1]=n-query(x-1, x);

   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);

      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);
      us[ans[i]]=true;
   }

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

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