제출 #204677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204677		Kastanda	Xylophone (JOI18_xylophone)	C++11	0 / 100	7 ms	632 KiB

xylophone

// In The Name Of The Queen
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int n;
vector < int > A, M;
inline int GetNext(int i)
{
    int df = query(i, i + 1);
    int v1 = A[i] - df;
    int v2 = A[i] + df;
    if (v1 < 1 || M[v1])
        return (v2);
    if (v2 > n || M[v2])
        return (v1);
    int Mn = A[i], Mx = A[i], j = i;
    for (j = i; v1 <= Mn && Mx <= v2; j --)
        Mn = min(Mn, A[j]),
        Mx = max(Mx, A[j]);
    df = query(j, i + 1);
    if (df == Mx - Mn)
        return (Mx <= v2 ? v1 : v2);
    return (Mx <= v2 ? v2 : v1);
}
inline int GetPrev(int i)
{
    int df = query(i - 1, i);
    int v1 = A[i] - df;
    int v2 = A[i] + df;
    if (v1 < 1 || M[v1])
        return (v2);
    if (v2 > n || M[v2])
        return (v1);
    int Mn = A[i], Mx = A[i], j = i;
    for (j = i; v1 <= Mn && Mx <= v2; j ++)
        Mn = min(Mn, A[j]),
        Mx = max(Mx, A[j]);
    df = query(i - 1, j);
    if (df == Mx - Mn)
        return (Mx <= v2 ? v1 : v2);
    return (Mx <= v2 ? v2 : v1);
}
void solve(int _n)
{
    n = _n;
    int le = 1, ri = n, md;
    while (ri - le > 1)
    {
        md = (le + ri) >> 1;
        if (query(md, n) == n - 1)
            le = md;
        else
            ri = md;
    }
    A = vector < int > (n + 1, 0);
    M = vector < int > (n + 1, 0);
    A[le] = 1; M[1] = 1;
    for (int i = le + 1; i <= n; i ++)
        A[i] = GetNext(i - 1), M[A[i]] = 1;
    for (int i = le - 1; i; i --)
        A[i] = GetPrev(i + 1), M[A[i]] = 1;
    for (int i = 1; i <= n; i ++)
        answer(i, A[i]);
}

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