Submission #734873

#	Time	Username	Problem	Language	Result	Execution time	Memory
734873		sandry24	Xylophone (JOI18_xylophone)	C++17	100 / 100	144 ms	380 KiB

xylophone

#include "xylophone.h"

void solve(int N){
    int diff1[N], diff2[N], A[N];
    for(int i = 0; i < N-1; i++)
        diff1[i] = query(i+1, i+2);
    for(int i = 0; i < N-2; i++)
        diff2[i] = query(i+1, i+3);
    A[0] = 0; A[1] = diff1[0];
    bool diffup = true;
    int maxpos = 1, minpos = 0;
    for(int i = 2; i < N; i++){
        if(diff1[i-2] + diff1[i-1] != diff2[i-2])
            diffup = !diffup;
        A[i] = A[i-1] + diff1[i-1] * (diffup ? 1 : -1);
        if(A[i] > A[maxpos])
            maxpos = i;
        if(A[i] < A[minpos])
            minpos = i;
    }
    if(maxpos < minpos){
        minpos = 1;
        A[1] = -diff1[0];
        bool diffup = false;
        for(int i = 2; i < N; i++){
            if(diff1[i-2] + diff1[i-1] != diff2[i-2])
                diffup = !diffup;
            A[i] = A[i-1] + diff1[i-1] * (diffup ? 1 : -1);
            if(A[i] < A[minpos])
                minpos = i;
        }
    }
    for(int i = 0; i < N; i++)
        answer(i+1, A[i] - A[minpos] + 1);
}

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