제출 #421478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421478		ACmachine	Xylophone (JOI18_xylophone)	C++17	100 / 100	376 ms	452 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i += (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
static int A[5000];

void solve(int N) {
    vector<array<int, 2>> nx(N + 1);
    FOR(i, 1, N + 1, 1){
        FOR(j, 1, 3, 1){
            if(i + j < N + 1){
                nx[i][j - 1] = query(i, i + j);
            }
        }
    }
    auto construct = [&](int f, int s){ // if I know prev 2, determines next; brute first. brute second as first + diff or first - diff; validate seq later
        vector<int> res(N + 1);
        res[1] = f;
        res[2] = s;
        FOR(i, 3, N + 1, 1){ 
            if(res[i - 2] > res[i - 1]){
                if(nx[i - 2][0] + nx[i - 1][0] == nx[i - 2][1]){
                    res[i] = res[i - 1] - nx[i - 1][0];
                } 
                else{
                    res[i] = res[i - 1] + nx[i - 1][0];
                }
            }
            else{
                if(nx[i - 2][0] + nx[i - 1][0] == nx[i - 2][1]){
                    res[i] = res[i - 1] + nx[i - 1][0];
                }
                else{
                    res[i] = res[i - 1] - nx[i - 1][0];
                }
            }
        }
        return res;
    };
    auto validate = [&](vector<int> &res){
        FOR(i, 1, N + 1, 1){
            if(res[i] > N || res[i] < 1)
                return false;
        }
        vector<bool> used(N + 1, false);
        FOR(i, 1, N + 1, 1){
            used[res[i]] = true;
        }
        FOR(i, 1, N + 1, 1){
            if(used[i] == false)
                return false;
        }
        int f = 0;
        int s = 0;
        FOR(i, 1, N + 1, 1){
            if(res[i] == 1)
                f = i;
            if(res[i] == N)
                s = i;
        }
        if(f > s)
            return false;
        return true;
    };
    vector<int> res;
    FOR(i, 1, N + 1, 1){
        res = construct(i, i + nx[1][0]);
        if(validate(res))
            break;
        res = construct(i, i - nx[1][0]);
        if(validate(res))
            break;
    }
    FOR(i, 1, N + 1, 1){
        answer(i, res[i]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

xylophone.cpp:9:12: warning: 'A' defined but not used [-Wunused-variable]
    9 | static int A[5000];
      |            ^

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