Submission #262385

#	Time	Username	Problem	Language	Result	Execution time	Memory
262385		Toirov_Sadi	Xylophone (JOI18_xylophone)	C++17	100 / 100	366 ms	560 KiB

xylophone

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

using namespace std;

const int N = 5e3 + 7;

int a[N];
int b[N];
int res[N];
bool check(int x, int y, int z, int a, int b){
    if(x <= 0) return 0;
    return (abs(x - y) == a && (max({x, y, z}) - min({x, y, z})) == b);
}
void solve(int N) {
    for(int i = 1; i < N; i ++){
        a[i] = query(i, i + 1);
    }
    for(int i = 1; i < N - 1; i ++){
        b[i] = query(i, i + 2);
    }
    for(int i = 1; i <= N; i ++){
        res[i] = 1;
        int good = 1;
        if(i > 1) res[i - 1] = a[i - 1] + 1;
        res[i + 1] = a[i] + 1;

        for(int j = i - 2; j >= 1; j --){
            int x = res[j + 1] - a[j];
            int y = res[j + 1] + a[j];
            if(check(x, res[j + 1], res[j + 2], a[j], b[j])) res[j] = x;
            else if(check(y, res[j + 1], res[j + 2], a[j], b[j])) res[j] = y;
            else good = 0;
        }

        for(int j = i + 2; j <= N; j ++){
            int x = res[j - 1] - a[j - 1];
            int y = res[j - 1] + a[j - 1];
            if(check(x, res[j - 1], res[j - 2], a[j - 1], b[j - 2])) res[j] = x;
            else if(check(y, res[j - 1], res[j - 2], a[j - 1], b[j - 2])) res[j] = y;
            else good = 0;
        }

        if(good == 1){
            for(int k = 1; k <= N; k ++){
                answer(k, res[k]);
            }
            return;
        }
    }
}

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