Submission #565668

#	Time	Username	Problem	Language	Result	Execution time	Memory
565668		shrimb	Xylophone (JOI18_xylophone)	C++17	47 / 100	79 ms	300 KiB

xylophone

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include "xylophone.h"
#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

// #define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 5001;
int nn;

int SET (int d, int a, bool inc) {
    int ret;
    if (inc) ret =  a + d;
    else ret = a - d;
    if (ret < 1 ||  ret > nn) return -1;
    return ret;
}

void solve (int n) {
    nn=n;
    int l = 1, r = n;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (query(m, n) == n - 1) l = m;
        else r = m;
    }
    int L = l;
    int A[n + 1];
    memset(A, -1, sizeof A);
    A[L] = 1;
    int dif = 0, inc = 1;
    for (int i = L - 1 ; i >= 1 ; i--) {
        int d = query(i, i + 1);
        if (i == L - 1) {
            A[i] = 1 + d;
            continue;
        }

        if (A[i + 1] < A[i + 2]) {
            if (query(i, i + 2) == d + A[i + 2] - A[i + 1]) {
                A[i] = A[i + 1] - d;
            } else {
                A[i] = A[i + 1] + d;
            }
        } else {
            if (query(i, i + 2) == d + A[i + 1] - A[i + 2]) {
                A[i] = A[i + 1] + d;
            } else {
                A[i] = A[i + 1] - d;
            }
        }
    }
    for (int i = L + 1 ; i <= n ; i++) {
        int d = query(i - 1, i);
        if (i == L + 1) {
            A[i] = 1 + d;
            continue;
        }

        if (A[i - 1] < A[i - 2]) {
            if (query(i - 2, i) == d + A[i - 2] - A[i - 1]) {
                A[i] = A[i - 1] - d;
            } else {
                A[i] = A[i - 1] + d;
            }
        } else {
            if (query(i - 2, i) == d + A[i - 1] - A[i - 2]) {
                A[i] = A[i - 1] + d;
            } else {
                A[i] = A[i - 1] - d;
            }
        }
    }
    // for (int i = 1 ; i <= n ; i++) cerr << A[i] << " ";
    for (int i = 1 ; i <= n ; i++) answer(i, A[i]);
}

Compilation message (stderr)

xylophone.cpp:18:1: warning: multi-line comment [-Wcomment]
   18 | //\
      | ^
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:44:9: warning: unused variable 'dif' [-Wunused-variable]
   44 |     int dif = 0, inc = 1;
      |         ^~~
xylophone.cpp:44:18: warning: unused variable 'inc' [-Wunused-variable]
   44 |     int dif = 0, inc = 1;
      |                  ^~~

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