Submission #200031

#	Time	Username	Problem	Language	Result	Execution time	Memory
200031		combi1k1	Xylophone (JOI18_xylophone)	C++14	100 / 100	102 ms	556 KiB

xylophone

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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

int a[N];
int d[N][2];

void solve(int n)   {
    d[2][0] = query(1,2);

    for(int i = 3 ; i <= n ; ++i)   {
        d[i][0] = query(i - 1,i);
        d[i][1] = query(i - 2,i);
    }
    a[2] = d[2][0];

    for(int i = 3 ; i <= n ; ++i)   {
        if (d[i][1] == d[i][0] + d[i - 1][0])   {
            if (a[i - 2] < a[i - 1])
                a[i] = a[i - 1] + d[i][0];
            else
                a[i] = a[i - 1] - d[i][0];
        }
        else    {
            if (a[i - 2] < a[i - 1])
                a[i] = a[i - 1] - d[i][0];
            else
                a[i] = a[i - 1] + d[i][0];
        }
    }
    int mn =  N;
    int mx = -N;

    for(int i = 1 ; i <= n ; ++i)   {
        if (mx < a[i])  mx = a[i];
        if (mn > a[i])  mn = a[i];
    }
    int cof = -mn + 1;
    int inv = 1;

    for(int i = 1 ; i <= n ; ++i)   {
        if (a[i] == mn) break;
        if (a[i] == mx) {
            inv = -1;
            cof = mx + 1;
            break;
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        answer(i,inv * a[i] + cof);
}

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