제출 #491563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491563		Alexandruabcde	Xylophone (JOI18_xylophone)	C++14	100 / 100	157 ms	552 KiB

xylophone

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

using namespace std;

constexpr int NMAX = 5005;

int D[NMAX];
int T[NMAX];

int val[NMAX];
int fr[NMAX];

int modul (int x) {
    if (x < 0) return -x;

    return x;
}

int FindThird (int a, int b, int ans_1, int ans_2, int ans_3) {
    int c = -1;
    if (ans_3 == ans_1) {
        if (b < a) c = b + ans_2;
        else c = b - ans_2;
    }
    else {
        c = b - ans_2;

        if (max(c, max(a, b)) - min(c, min(a, b)) == ans_3 && c > 0) return c;
        else c = b + ans_2;
    }

    return c;
}

void solve(int N) {
    for (int i = 1; i < N; ++ i )
        D[i] = query(i, i+1);
    for (int i = 1; i < N-1; ++ i )
        T[i] = query(i, i+2);

    for (int i = 1; i <= N; ++ i ) {
        val[i] = N;
        for (int j = 0; j <= N; ++ j )
            fr[j] = 0;

        fr[val[i]]++;
        bool ok = 1;

        if (i != N)
            val[i+1] = val[i] - D[i];
        if (i != 1)
            val[i-1] = val[i] - D[i-1];

        fr[val[i-1]]++;
        fr[val[i+1]]++;

        if (fr[val[i-1]] > 1 || fr[val[i+1]] > 1) continue;

        for (int j = i + 2; j <= N; ++ j ) {
            val[j] = FindThird(val[j-2], val[j-1], D[j-2], D[j-1], T[j-2]);

            if (val[j] < 1 || val[j] > N || fr[val[j]] > 0) {
                ok = false;
                break;
            }
            fr[val[j]]++;
        }

        for (int j = i-2; j >= 1; -- j ) {
            val[j] = FindThird(val[j+2], val[j+1], D[j+1], D[j], T[j]);

            if (val[j] < 1 || val[j] > N || fr[val[j]] > 0) {
                ok = false;
                break;
            }
            fr[val[j]]++;
        }

        if (ok) {
            int poz_1 = 0, poz_N = i;
            for (int j = 1; j <= N; ++ j )
                if (val[j] == 1) poz_1 = j;

            if (poz_1 > poz_N) continue;

            for (int j = 1; j <= N; ++ j )
                answer(j, val[j]);
            break;
        }
    }
}

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