# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
870400 | 2023-11-07T17:13:02 Z | serifefedartar | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9+9; const ll LOGN = 20; const ll MAXN = 5e3 + 100; int qry[MAXN][MAXN]; int diff[MAXN]; void solve(int N) { for (int i = 1; i <= N - 1; i++) qry[i][i+1] = query(i, i+1); for (int i = 1; i <= N - 2; i++) qry[i][i+2] = query(i, i+2); diff[2] = qry[1][2]; for (int i = 1; i <= N - 2; i++) { if (qry[i][i+1] + qry[i+1][i+2] == qry[i][i+2]) { if (diff[i] < diff[i+1]) diff[i+2] = diff[i+1] + qry[i+1][i+2]; else diff[i+2] = diff[i+1] - qry[i+1][i+2]; } else { if (diff[i] < diff[i+1]) diff[i+2] = diff[i+1] - qry[i+1][i+2]; else diff[i+2] = diff[i+1] + qry[i+1][i+2]; } } int mn = 1, mx = 1; for (int i = 2; i <= N; i++) { if (diff[i] < diff[mn]) mn = i; if (diff[i] > diff[mx]) mx = i; } if (mn > mx) { for (int i = 1; i <= N; i++) diff[i] = -diff[i]; } int sum = 0; for (int i = 1; i <= N; i++) sum += diff[i]; int con = (N * (N + 1) / 2 - sum) / N; for (int i = 1; i <= N; i++) answer(i, con + diff[i]); }