Submission #552554

#	Time	Username	Problem	Language	Result	Execution time	Memory
552554		RaresFelix	Xylophone (JOI18_xylophone)	C++17	100 / 100	105 ms	592 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
int n;
void solve(int N) {
    n = N;
    if(n == 2) {
        answer(1, 1), answer(2, 2);
        return;
    }
    vector<int> R1, R2, Tip;
    for(int i = 1; i < n; ++i) R1.push_back(query(i, i + 1));
    for(int i = 1; i < n - 1; ++i) R2.push_back(query(i, i + 2));
    Tip.push_back(1);
    for(int i = 1; i < n - 1; ++i) {
        if(R2[i-1] != R1[i-1] + R1[i]) Tip.push_back(-Tip.back());
        else Tip.push_back(Tip.back());
    }
    vector<int> Dif;
    for(int i = 1; i < n; ++i)
        Dif.push_back(R1[i-1] * Tip[i-1]);
    vector<int> R;
    R.push_back(0);
    int mi = 0;
    for(int i = 0; i < n - 1; ++i){
        R.push_back(R.back() + Dif[i]);
        mi = min(mi, R.back());
    }
    for(int i = 0; i < n; ++i) R[i] -= mi - 1;
    int ok = 1;
    for(int i = 0; i < n; ++i) {
        if(R[i] == 1) break;
        if(R[i] == n) {
            ok = 0;
            break;
        }
    }
    if(!ok)
        for(auto &it : R) it = n - it + 1;
    for(int i = 0; i < n; ++i) answer(i + 1, R[i]);
}

Compilation message (stderr)

xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
    4 | static int A[5000];
      |            ^

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