# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1257097 | Thunnus | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
// index[1] < index[n]
void solve(int n){
vi diff(n + 1);
for(int i = 2; i <= n; i++){
diff[i] = query(i - 1, i);
if(i - 2 >= 1){
int tri = query(i - 2, i);
if(tri != diff[i] + diff[i - 1]){
diff[i] = -diff[i]; // change direction, increasing->decreasing or decreasing->increasing
}
}
}
vi pref(n + 1);
int mn = 1, mx = 1;
for(int i = 2; i <= n; i++){
pref[i] = diff[i] + pref[i - 1];
if(pref[i] > pref[mx]){
mx = i;
}
else if(pref[i] < pref[mn]){
mn = i;
}
}
if(mn > mx){ // index[1] (mn) < index[n] (mx)
for(int i = 2; i <= n; i++){
diff[i] = -diff[i];
}
swap(mn, mx);
}
vi ans(n + 1);
ans[mx] = n, ans[mn] = 1;
for(int i = mx - 1; i >= 1; i--){
ans[i] = ans[i + 1] - diff[i + 1];
}
for(int i = mx + 1; i <= n; i++){
ans[i] = ans[i - 1] + diff[i];
}
for(int i = 1; i <= n; i++){
answer(i, ans[i]);
}
return;
}