Submission #70868

#	Time	Username	Problem	Language	Result	Execution time	Memory
70868		ASG1065	Xylophone (JOI18_xylophone)	C++14	100 / 100	105 ms	720 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

static int A[5000];
int pitch[5001];
bool used[5001];
int n;

int binarySearchn()
{
    int lo = 1;
    int hi = n;
    while (1)
    {
        int mid = (hi+lo)/2;
        if (hi == lo) return lo;
        if (query(1,mid) == n-1) hi = mid;
        else lo = mid+1;
    }
    return -1;
}

int binarySearch1()
{
    int lo = 1;
    int hi = n;
    while (1)
    {
        int mid = (hi+lo)/2 + (hi+lo)%2;
        if (hi == lo) return lo;
        if (query(mid, n) == n-1) lo = mid;
        else hi = mid-1;
    }
    return -1;
}

void solve(int N)
{
    n = N;
    std::memset(pitch, 0, sizeof pitch);
    std::memset(used, false, sizeof used);
    int smallest = binarySearch1();
    int biggest = binarySearchn();
    pitch[smallest] = 1;
    pitch[biggest] = n;
    used[1] = true;
    used[n] = true;
    int a = query(smallest, smallest+1);
    pitch[smallest+1] = 1+a;
    used[a+1] = true;
    int b = query(biggest-1, biggest);
    pitch[biggest-1] = n-b;
    used[n-b] = true;
    for (int i = smallest-1; i >=1; --i)
    {
        int diff = query(i, i+1);
        int option1 = pitch[i+1] - diff;
        int option2 = pitch[i+1] + diff;
        if (option1 < 1 || used[option1]) {used[option2] = true; pitch[i] = option2;}
        else if (option2 > n || used[option2]) {used[option1] = true; pitch[i] = option1;}
        else
        {
            int z = query(i, i+2);
            if (std::max(std::max(std::abs(option1-pitch[i+1]), std::abs(pitch[i+1]-pitch[i+2])), std::abs(pitch[i+2]-option1)) == z)
            {
                used[option1] = true;
                pitch[i] = option1;
            }
            else
            {
                used[option2] = true;
                pitch[i] = option2;
            }
        }
    }
    for (int i = biggest+1; i <= n; ++i)
    {
        int diff = query(i-1, i);
        int option1 = pitch[i-1] - diff;
        int option2 = pitch[i-1] + diff;
        if (option1 < 1 || used[option1]) {used[option2] = true; pitch[i] = option2;}
        else if (option2 > n || used[option2]) {used[option1] = true; pitch[i] = option1;}
        else
        {
            int z = query(i-2, i);
            if (std::max(std::max(std::abs(option1-pitch[i-1]), std::abs(pitch[i-1]-pitch[i-2])), std::abs(pitch[i-2]-option1)) == z)
            {
                used[option1] = true;
                pitch[i] = option1;
            }
            else
            {
                used[option2] = true;
                pitch[i] = option2;
            }
        }
    }
    for (int i = smallest+2; i <= biggest-2; ++i)
    {
        int diff = query(i-1, i);
        int option1 = pitch[i-1] - diff;
        int option2 = pitch[i-1] + diff;
        if (option1 < 1 || used[option1]) {used[option2] = true; pitch[i] = option2;}
        else if (option2 > n || used[option2]) {used[option1] = true; pitch[i] = option1;}
        else
        {
            int z = query(i-2, i);
            if (std::max(std::max(std::abs(option1-pitch[i-1]), std::abs(pitch[i-1]-pitch[i-2])), std::abs(pitch[i-2]-option1)) == z)
            {
                used[option1] = true;
                pitch[i] = option1;
            }
            else
            {
                used[option2] = true;
                pitch[i] = option2;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        answer(i, pitch[i]);
    }
}

Compilation message (stderr)

xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
 static int A[5000];
            ^

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