Submission #763038

#	Time	Username	Problem	Language	Result	Execution time	Memory
763038		vjudge1	Xylophone (JOI18_xylophone)	C++17	100 / 100	87 ms	552 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
int a[5001], ans[5001];
bool dif[5001];
void solve(int n)
{
    if(n == 2){
        answer(1, 1);
        answer(2, 2);
        return;
    }
    for(int i = 1; i < n; i++) a[i] = query(i, i+1);
    for(int i = 1; i < n-1; i++){
        int x = query(i, i+2);
        if(x == a[i] + a[i+1]) dif[i] = 0;
        else dif[i] = 1;
    }
    bool anssign = 0, sign = 0;
    int maximum = 0, maxplace = 0, minimum = 0, minplace = 0, cur = 0;
    for(int i = 1; i < n; i++){
        if(sign == 0) cur -= a[i];
        else cur += a[i];
        if(maximum < cur){
            maximum = cur;
            maxplace = i+1;
        }
        if(minimum > cur){
            minimum = cur;
            minplace = i+1;
        }
        sign ^= dif[i];
    }
    if(maxplace > minplace) anssign = 0;
    else anssign = 1;
    minimum = 0; cur = 0;
    for(int i = 1; i < n; i++){
        if(anssign == 0) cur -= a[i];
        else cur += a[i];
        minimum = min(minimum, cur);
        anssign ^= dif[i];
        ans[i+1] = cur;
    }
    for(int i = 1; i <= n; i++){
        ans[i] += -minimum+1;
        answer(i, ans[i]);
    }
    return;
}

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