Submission #163730

#	Time	Username	Problem	Language	Result	Execution time	Memory
163730		DS007	Xylophone (JOI18_xylophone)	C++14	100 / 100	79 ms	484 KiB

xylophone

#include <bits/stdc++.h>
using namespace std;

int query(int u, int v);
void answer(int u, int v);
/*void solve(int n);
int main() {
    solve(69);
}*/

void solve(int n) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int d = query(1, n);
    int l = 1, h = n, ans1 = -1;
    while (l <= h) {
        int m = (l + h) / 2;
        if (query(1, m) == d)
            ans1 = m, h = m - 1;
        else
            l = m + 1;
    }

    int a[n];
    a[ans1 - 1] = n;

    /*int ans2 = -1;
    l = 1, h = ans1 - 1;
    while (l <= h) {
        int m = (l + h) / 2;
        if (query(m, ans1) == d)
            ans2 = m, l = m + 1;
        else
            h = m - 1;
    }
    a[ans2 - 1] = 1;*/

    bool check[n];
    fill(check, check + n, false);
    check[n - 1] = true;

    if (ans1 != n)
        a[ans1] = n - query(ans1, ans1 + 1), check[a[ans1] - 1] = true;
    a[ans1 - 2] = n - query(ans1 - 1, ans1);
    check[a[ans1 - 2] - 1] = true;

    for (int i = ans1 + 1; i < n; i++) {
        int d1 = query(i, i + 1);
        if (a[i - 1] + d1 >= n || check[a[i - 1] + d1 - 1]) {
            a[i] = a[i - 1] - d1, check[a[i] - 1] = true;
            continue;
        } else if (a[i - 1] - d1 <= 1 || check[a[i - 1] - d1 - 1]) {
            a[i] = a[i - 1] + d1, check[a[i] - 1] = true;
            continue;
        }
        int d2 = query(i - 1, i + 1);
        if (d2 == abs(a[i - 1] - a[i - 2])) {
            if (a[i - 1] > a[i - 2])
                a[i] = a[i - 1] - d1;
            else
                a[i] = a[i - 1] + d1;
        } else {
            int temp = a[i - 1] + d1;
            if (max(temp, max(a[i - 1], a[i - 2])) - min(temp, min(a[i - 1], a[i - 2])) == d2)
                a[i] = temp;
            else
                a[i] = temp - 2 * d1;
        }
        check[a[i] - 1] = true;
    }

    for (int i = ans1 - 3; i >= 0; i--) {
        int d1 = query(i + 1, i + 2);
        if (a[i + 1] + d1 >= n || check[a[i + 1] + d1 - 1]) {
            a[i] = a[i + 1] - d1, check[a[i] - 1] = true;
            continue;
        } else if (a[i + 1] - d1 < 1 || check[a[i + 1] - d1 - 1]) {
            a[i] = a[i + 1] + d1, check[a[i] - 1] = true;
            continue;
        }
        int d2 = query(i + 1, i + 3);
        if (d2 == abs(a[i + 1] - a[i + 2])) {
            if (a[i + 1] > a[i + 2])
                a[i] = a[i + 1] - d1;
            else
                a[i] = a[i + 1] + d1;
        } else {
            int temp = a[i + 1] + d1;
            if (max(temp, max(a[i + 1], a[i + 2])) - min(temp, min(a[i + 1], a[i + 2])) == d2)
                a[i] = temp;
            else
                a[i] = temp - 2 * d1;
        }
        check[a[i] - 1] = true;
    }

    for (int i = 1; i <= n; i++)
        answer(i, a[i - 1]);
}
/*
#include <cstdio>
#include <cstdlib>

static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;

int query(int s, int t) {
    if(query_c >= Q_MAX) {
        printf("Wrong Answer\n");
        exit(0);
    }
    query_c++;
    if(!(1 <= s && s <= t && t <= N)) {
        printf("Wrong Answer\n");
        exit(0);
    }
    int mx = 0, mn = N + 1;
    for(int i = s - 1; i < t; i++) {
        if(mx < A[i]) {
            mx = A[i];
        }
        if(mn > A[i]) {
            mn = A[i];
        }
    }
    return mx - mn;
}

void answer(int i, int a) {
    answer_c++;
    if(!(1 <= i && i <= N)) {
        printf("Wrong Answer\n");
        exit(0);
    }
    if(!(1 <= a && a <= N)) {
        printf("Wrong Answer\n");
        exit(0);
    }
    if(used[i - 1]) {
        printf("Wrong Answer\n");
        exit(0);
    }
    if(a != A[i - 1]) {
        printf("Wrong Answer\n");
        exit(0);
    }
    used[i - 1] = true;
}

int main() {
    query_c = 0;
    answer_c = 0;
    if(scanf("%d", &N) != 1) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    for(int i = 0; i < N; i++) {
        if(scanf("%d", A + i) != 1) {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        used[i] = false;
    }
    solve(N);
    if(!(answer_c == N)) {
        printf("Wrong Answer\n");
        exit(0);
    }
    printf("Accepted : %d\n", query_c);
}
*/

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