Submission #232012

#	Time	Username	Problem	Language	Result	Execution time	Memory
232012		alexandra_udristoiu	Xylophone (JOI18_xylophone)	C++14	100 / 100	73 ms	632 KiB

xylophone

#include<iostream>
#include "xylophone.h"
using namespace std;
static int v[5005], viz[5005], dif[5005];

void solve(int n) {
    int i, st, dr, mid, d, d3, p;
    st = 1;
    dr = n;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(query(mid, n) == n - 1){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    p = dr;
    v[p] = viz[1] = 1;
    for(i = p - 1; i >= 1; i--){
        d = query(i, i + 1);
        if(v[i + 1] - d < 1 || viz[ v[i + 1] - d ] == 1){
            v[i] = v[i + 1] + d;
        }
        else{
            if(v[i + 1] + d > n || viz[ v[i + 1] + d ] == 1){
                v[i] = v[i + 1] - d;
            }
            else{
                d3 = query(i, i + 2);
                if(d3 == d + dif[i + 1]){
                    if(v[i + 2] > v[i + 1]){
                        v[i] = v[i + 1] - d;
                    }
                    else{
                        v[i] = v[i + 1] + d;
                    }
                }
                else{
                    if(v[i + 2] < v[i + 1]){
                        v[i] = v[i + 1] - d;
                    }
                    else{
                        v[i] = v[i + 1] + d;
                    }
                }
            }
        }
        dif[i] = d;
        viz[ v[i] ] = 1;
    }
    for(i = p + 1; i <= n; i++){
        d = query(i - 1, i);
        if(v[i - 1] - d < 1 || viz[ v[i - 1] - d ] == 1){
            v[i] = v[i - 1] + d;
        }
        else{
            if(v[i - 1] + d > n || viz[ v[i - 1] + d ] == 1){
                v[i] = v[i - 1] - d;
            }
            else{
                d3 = query(i - 2, i);
                if(d3 == d + dif[i - 1]){
                    if(v[i - 2] > v[i - 1]){
                        v[i] = v[i - 1] - d;
                    }
                    else{
                        v[i] = v[i - 1] + d;
                    }
                }
                else{
                    if(v[i - 2] < v[i - 1]){
                        v[i] = v[i - 1] - d;
                    }
                    else{
                        v[i] = v[i - 1] + d;
                    }
                }
            }
        }
        dif[i] = d;
        viz[ v[i] ] = 1;
    }
    for(i = 1; i <= n; i++){
        answer(i, v[i]);
    }
    return;
}

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