oj.uz

답안 #204677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204677 2020-02-26T15:24:32 Z Kastanda Xylophone (JOI18_xylophone) C++11
0 / 100
 7 ms 632 KB 
// 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Runtime error 7 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -