Submission #528448

#	Time	Username	Problem	Language	Result	Execution time	Memory
528448		AdamGS	Xylophone (JOI18_xylophone)	C++17	100 / 100	102 ms	540 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=5e5+7;
int A[LIM], B[LIM], rodzaj[LIM], T[LIM];
void solve(int n) {
    rep(i, n-1) A[i]=query(i+1, i+2);
    rep(i, n-2) B[i]=query(i+1, i+3);
    rep(i, n-2) if(A[i]+A[i+1]!=B[i]) rodzaj[i+1]=rodzaj[i]^1; else rodzaj[i+1]=rodzaj[i];
    rep(i, n-1) {
        if(rodzaj[i]) T[i+1]=T[i]+A[i];
        else T[i+1]=T[i]-A[i];
    }
    int mi=LIM, ma=-LIM, ind1=-1, ind2=-1;
    rep(i, n) {
        if(T[i]<mi) {
            mi=T[i];
            ind1=i;
        }
        if(T[i]>ma) {
            ma=T[i];
            ind2=i;
        }
    }
    if(ind1<ind2) {
        rep(i, n) answer(i+1, T[i]-mi+1);
        return;
    }
    rep(i, n-1) {
        if(rodzaj[i]) T[i+1]=T[i]-A[i];
        else T[i+1]=T[i]+A[i];
    }
    mi=LIM;
    rep(i, n) mi=min(mi, T[i]);
    rep(i, n) answer(i+1, T[i]-mi+1);
}

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