Submission #565634

#	Time	Username	Problem	Language	Result	Execution time	Memory
565634		shrimb	Xylophone (JOI18_xylophone)	C++17	0 / 100	2 ms	208 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;

void solve (int 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;
    l = L, r = n;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (query(L, m) == n - 1) r = m;
        else l = m;
    }
    int R = r; 
    int dif = 0;
    int A[n + 1];
    A[L] = 1;
    A[R] = n;
    for (int i = L - 1 ; i >= 1 ; i--) {
        int d = query(i, L);
        if (d != dif) A[i] = d + 1;
        dif = d;
    }
    dif = 0;
    for (int i = L + 1 ; i < R ; i++) {
        int d = query(L, i);
        if (d != dif) A[i] = d + 1;
        dif = d;
    }
    dif = 0;
    for (int i = R + 1 ; i <= n ; i++) {
        int d = query(R, i);
        if (d != dif) A[i] = n  - d;
        dif = d;
    }
    dif = 0;
    for (int i = R - 1; i > L ; i--) {
        int d = query(i, R);
        if (d != dif) A[i] = n - d;
        dif = d;
    }
    for (int i = 1 ; i <= n ; i++) answer(i, A[i]);
}

Compilation message (stderr)

xylophone.cpp:18:1: warning: multi-line comment [-Wcomment]
   18 | //\
      | ^

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