Submission #95393

#	Time	Username	Problem	Language	Result	Execution time	Memory
95393		onjo0127	Xylophone (JOI18_xylophone)	C++11	100 / 100	179 ms	98680 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

int m[5009][5009], A[5009], D[5009];

int get(int s, int t) {
    if(s == t) return 0;
    if(m[s][t] == -1) m[s][t] = query(s, t);
    return m[s][t];
}

void solve(int N) {
    memset(m, -1, sizeof(m));
    A[1] = 0; A[2] = get(1, 2);
    bool inc = 1;
    for(int i=3; i<=N; i++) {
        if(inc) {
            if(get(i-2, i-1) == get(i-2, i)) A[i] = A[i-1] - get(i-1, i), inc = 0;
            else {
                if(A[i-2] + get(i-2, i) == A[i-1] + get(i-1, i)) A[i] = A[i-1] + get(i-1, i);
                else A[i] = A[i-1] - get(i-1, i), inc = 0;
            }
        }
        else {
            if(get(i-2, i-1) == get(i-2, i)) A[i] = A[i-1] + get(i-1, i), inc = 1;
            else {
                if(A[i-2] - get(i-2, i) == A[i-1] - get(i-1, i)) A[i] = A[i-1] - get(i-1, i);
                else A[i] = A[i-1] + get(i-1, i), inc = 1;
            }
        }
    }
    int mn = 1, mx = 1;
    for(int i=1; i<=N; i++) {
        if(A[mn] > A[i]) mn = i;
        if(A[mx] < A[i]) mx = i;
        D[i] = A[i] - A[i-1];
    }
    if(mn > mx) {
        for(int i=2, s=0; i<=N; i++) s += -D[i], A[i] = s;
        swap(mn, mx);
    }
    for(int i=1; i<=N; i++) answer(i, A[i] - A[mn] + 1);
}

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