제출 #1368901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368901		altern23	Xylophone (JOI18_xylophone)	C++20	100 / 100	16 ms	460 KiB

xylophone

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

#define ll long long

void solve(int N) {
      ll lf = 1, rg = N, ptr = -1;
      while (lf<=rg) {
            ll mid = (lf+rg)/2;
            if (query(1, mid) == N-1) {
                  ptr = mid;
                  rg = mid-1;
            }
            else lf = mid+1;
      }

      vector <ll> A(N+5);
      vector <bool> vtd(N+5);

      A[ptr] = N;
      vtd[N] = 1;

      // tentuin yang kanan
      ll lst = -1;
      bool arah = 0;

      if (ptr+1 <= N) {
            lst = query(ptr, ptr+1);
            A[ptr+1] = N-lst;
            vtd[A[ptr+1]] = 1;
      }
      
      for (int i=ptr+2; i<=N; i++) {
            ll z = query(i-1, i);
            if (A[i-1]-z >= 1 && vtd[A[i-1]-z]) {
                  A[i] = A[i-1]+z;
                  vtd[A[i]] = 1;
                  arah = (A[i]>A[i-1]);
                  lst = z;
                  continue;
            }
            if (A[i-1]+z <= N && vtd[A[i-1]+z]) {
                  A[i] = A[i-1]-z;
                  vtd[A[i]] = 1;
                  arah = (A[i]>A[i-1]);
                  lst = z;
                  continue;
            }
            ll y = query(i-2, i);
            if (z+lst != y) arah ^= 1;
            if (!arah) A[i] = A[i-1]-z;
            else A[i] = A[i-1]+z;
            lst = z;
            vtd[A[i]] = 1;
      }

      // tentuin yg kiri
      arah = 0;
      if (ptr-1 >= 1) {
            lst = query(ptr-1, ptr);
            A[ptr-1] = N-lst;
            vtd[A[ptr-1]] = 1;
      }

      for (int i=ptr-2; i>=1; --i) {
            ll z = query(i, i+1);
            if (A[i+1]-z >= 1 && vtd[A[i+1]-z]) {
                  A[i] = A[i+1]+z;
                  vtd[A[i]] = 1;
                  arah = (A[i]>A[i+1]);
                  lst = z;
                  continue;
            }
            if (A[i+1]+z <= N && vtd[A[i+1]+z]) {
                  A[i] = A[i+1]-z;
                  vtd[A[i]] = 1;
                  arah = (A[i]>A[i+1]);
                  lst = z;
                  continue;
            }
            ll y = query(i, i+2);
            if (z+lst != y) arah ^= 1;
            if (!arah) A[i] = A[i+1]-z;
            else A[i] = A[i+1]+z;
            lst = z;
            vtd[A[i]] = 1;
      }
      
      for (int i=1; i<=N; i++) {
            answer(i, A[i]);
      }
}

• 서브태스크 1: 11 / 11
• 서브태스크 2: 36 / 36
• 서브태스크 3: 53 / 53