Submission #502956

#	Time	Username	Problem	Language	Result	Execution time	Memory
502956		Marduk	Xylophone (JOI18_xylophone)	C++14	0 / 100	0 ms	200 KiB

xylophone

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

const int MAXN = (1e4+7);

bool arr[MAXN];
int memo_d[MAXN], memo_t[MAXN];
int sol[MAXN];

int D(int x){
    if(memo_d[x]) return memo_d[x];
    return memo_d[x] = query(x, x+1);
}

int T(int x){
    if(memo_t[x]) return memo_t[x];
    return memo_t[x] = query(x, x+2);
}

void solve(int N){

    arr[2] = true;
    for(int i = 1;i<=N-2;i++){

        if(D(i)+D(i+1) == T(i)) arr[i+2] = true;
        else arr[i+2] = false;
    }

    for(int i = 0;i<2;i++){
        int MIN = MAXN;
        for(int i = 2;i<=N;i++){
            sol[i] = sol[i-1] + (arr[i]%2-(arr[i]+1)%2)*D(i-1);
            MIN = min(MIN,sol[i]);
            arr[i] = !arr[i];
        }

        bool found = 0;
        for(int i = 1;i<=N;i++){
            if(sol[i]+(1-MIN) == 1) break;
            if(sol[i]+(1-MIN) == N) {found = 1; break;}
        }

        if(!found){
            for(int i = 1;i<=N;i++) answer(i,sol[i]+(1-MIN));
            return;
        }
    }
}

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