Submission #565971

#	Time	Username	Problem	Language	Result	Execution time	Memory
565971		birthdaycake	Xylophone (JOI18_xylophone)	C++17	100 / 100	107 ms	20632 KiB

xylophone

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


int A[5001][5001];
int ans[5001],sign[20001];


void solve(int n) {
    
    // query(i, i + 2) = query(i, i + 1) + query(i + 1, i + 2)
    // a[i] < a[i + 1] < a[i + 2]
    // a[i] > a[i + 1] > a[i + 2]
    
    
    
    // query(i, i + 2) != query(i, i + 1) + query(i + 1, i + 2)
    
    // a[i] > a[i + 1] < a[i + 2]
    // a[i] < a[i + 1] > a[i + 2]
    
    
    for(int i = 1; i <= n; i++){
        int x = - 1, y = -1;
        if(i + 1 <= n) x = query(i, i + 1);
        if(i + 2 <= n) y = query(i, i + 2);
        A[i][0] = x;
        A[i][1] = y;
    }
    // < A[i] > A[i + 1] > A[i + 2]
    sign[1] = 1;
    
    
    // a[i] > a[i + 1]
    
    // if q == q + q
    // equal to prev sign
    // else
    // opposite sign
    
    
    
    
    for(int i = 2; i < n; i++){
        // sign[i] = sign between i, i + 1
        if(A[i - 1][0] + A[i][0] == A[i - 1][1]){
            sign[i] = sign[i - 1];
        }else{
            sign[i] = !sign[i - 1];
        }
    }
    
    
    ans[1] = 0;
    for(int i = 1; i < n; i++){
        if(sign[i] == 1){
            ans[i + 1] = ans[i] - A[i][0];
        }else{
            ans[i + 1] = ans[i] + A[i][0];
        }
    }
    int mn = 1e9;
    for(int i = 1; i <= n; i++){
        mn = min(mn,ans[i]);
    }
    for(int i = 1; i <= n; i++) ans[i] += (1 - mn);
    
    int f = 0, bad = 0;
    for(int i = 1; i <= n; i++){
        if(ans[i] == 1 && f) bad = 1;
        if(ans[i] == n) f = 1;
    }
    if(bad){
        for(int i = 1; i <= n; i++){
            ans[i] = n + 1 - ans[i];
        }
    }
    for(int i = 1; i <= n; i++){
        answer(i,ans[i]);
    }
    
}

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