제출 #113301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113301		popovicirobert	Xylophone (JOI18_xylophone)	C++14	47 / 100	54 ms	412 KiB

xylophone

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

using namespace std;

//static int A[5000];

int cnt = 0;

inline int get(int a, int b, int pa, int pb, int pc) {

    cnt += 2;

    if(cnt > 10000) {
        while(1) {

        }
    }

    int bc = query(min(pb, pc), max(pb, pc)), ac = query(min(pa, pc), max(pa, pc));

    if(a < b) {
        if(bc == ac) {
            return b - bc;
        }
        if(ac == abs(a - b)) {
            return b - bc;
        }
        return b + bc;
    }
    else {
        if(bc == ac) {
            return b + bc;
        }
        if(ac == abs(a - b)) {
            return b + bc;
        }
        return b - bc;
    }
}

void solve(int n) {

    int pos = n + 1, i;

    for(int step = 1 << 15; step; step >>= 1) {
        if(pos - step >= 1 && query(pos - step, n) < n - 1) {
            pos -= step;
        }
    }

    pos--; // 1

    vector <int> sol(n + 2);

    sol[pos] = 1;

    if(pos > 1) {
        sol[pos - 1] = 1 + query(pos - 1, pos);
    }

    int a = sol[pos], b = sol[pos - 1];

    for(i = pos - 2; i >= 1; i--) {
        int c = get(a, b, i + 2, i + 1, i);
        sol[i] = c;
        a = b;
        b = c;
    }

    if(pos < n) {
        sol[pos + 1] = 1 + query(pos, pos + 1);
    }

    a = sol[pos], b = sol[pos + 1];

    for(i = pos + 2; i <= n; i++) {
        int c = get(a, b, i - 2, i - 1, i);
        sol[i] = c;
        a = b;
        b = c;
    }

    for(i = 1; i <= n; i++) {
        answer(i, sol[i]);
    }

}

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