Submission #156356

#	Time	Username	Problem	Language	Result	Execution time	Memory
156356		georgerapeanu	Xylophone (JOI18_xylophone)	C++11	47 / 100	99 ms	504 KiB

xylophone

#include "xylophone.h"
#include <cstdio>

using namespace std;

static int a[5005];

void solve(int n) {

    int l = 1,r = n;

    while(r - l > 1){
        int mid = (l + r) / 2;
        if(query(1,mid) == n - 1){
            r = mid;
        }
        else{
            l = mid;
        }
    }

    int pos_n = r;
    a[pos_n] = n;

    for(int i = pos_n + 1;i <= n;i++){
        int delta = query(i - 1,i);
        if(a[i - 1] + delta > n){
            a[i] = a[i - 1] - delta;
        }
        else if(a[i - 1] - delta < 1){
            a[i] = a[i - 1] + delta;
        }
        else{
            int delta2 = query(i - 2,i);
            if(delta2 == delta){
                a[i] = (a[i - 1] <= a[i - 2] ? delta:-delta) + a[i - 1];
            }
            else{
                if(a[i - 1] + delta == a[i - 2] + delta2 || a[i - 1] + delta == a[i - 2] - delta2){
                    a[i] = a[i - 1] + delta;
                }
                else if(a[i - 1] - delta == a[i - 2] + delta2 || a[i - 1] - delta == a[i - 2] -delta2){
                    a[i] = a[i - 1] - delta;
                }
                else{
                    a[i] = a[i - 1] + (a[i - 1] < a[i - 2] ? delta:-delta);
                }
            }
        }
    }
    
    for(int i = pos_n - 1;i;i--){
        int delta = query(i,i + 1);
        if(a[i + 1] + delta > n){
            a[i] = a[i + 1] - delta;
        }
        else if(a[i + 1] - delta < 1){
            a[i] = a[i + 1] + delta;
        }
        else{
            int delta2 = query(i,i + 2);
            if(delta2 == delta){
                a[i] = (a[i + 1] <= a[i + 2] ? delta:-delta) + a[i + 1];
            }
            else{
                if(a[i + 1] + delta == a[i + 2] + delta2 || a[i + 1] + delta == a[i + 2] - delta2){
                    a[i] = a[i + 1] + delta;
                }
                else if(a[i + 1] - delta == a[i + 2] + delta2 || a[i + 1] - delta == a[i + 2] -delta2){
                    a[i] = a[i + 1] - delta;
                }
                else{
                    a[i] = a[i + 1] + (a[i + 1] < a[i + 2] ? delta:-delta);
                }
            }
        }
    }

    for(int i = 1;i <= n;i++){
        answer(i,a[i]);
    }
}

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