Submission #156354

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

xylophone

#include "xylophone.h"

using namespace std;

static int a[5005];

void get_val(int st,int dr,int st_val,int dr_val,int target_val,bool mode){
    if(st == dr){
        return ;
    }

    int l = st,r = dr;
    
    if(st_val != -1){
        while(r - l > 1){
            int mid = (l + r) / 2;
            if(query(st,mid) < target_val){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        a[r] = st_val + (mode == false ? -1:1) * target_val;
        get_val(st + 1,r,-1,a[r],query(st + 1,r),!mode);
        get_val(r,dr,a[r],-1,query(r,dr),!mode);
    }
    else{
        while(r - l > 1){
            int mid = (l + r) / 2;
            if(query(mid,dr) < target_val){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        a[l] = dr_val + (mode == false ? -1:1) * target_val;
        get_val(st,l,-1,a[l],query(st,l),!mode);
        get_val(l,dr - 1,a[l],-1,query(l,dr - 1),!mode);
    }
}
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;

    get_val(1,pos_n,-1,n,query(1,pos_n),false);
    get_val(pos_n,n,n,-1,query(pos_n,n),false);

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

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