| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 891270 | vjudge1 | Bitaro's travel (JOI23_travel) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
int n;
vector<int> a;
int solve(int l, int r, bool direction) {
int p = x[direction ? r : l];
if (l == 0) {
return x[n - 1] - p;
} else if (r == n - 1) {
return p - x[0];
} else if (p - x[l - 1] <= x[r + 1] - p) {
int q = lower_bound(all(x), 2 * p - x[r + 1]) - x.begin();
return p - x[q] + solve(q, r, false);
} else {
int q = upper_bound(all(x), 2 * p - x[l - 1]) - x.begin() - 1;
return x[q] - p + solve(l, q, true);
}
}
int solve(int l, int r, int x){
if(l <= 0){
return a[n-1] - x;
}else if(r >= n-1){
return x - a[0];
}else if(abs(a[l-1] - x) <= abs(a[r+1] - x)){
int q = lower_bound(all(a), x * 2 - a[r+1]) - a.begin();
return x - a[q] + solve(q, r, a[q]);
}else{
int q = upper_bound(all(a), x * 2 - a[l-1]) - a.begin() - 1;
return a[q] - x + solve(l, q, a[q]);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
a.resize(n);
for(auto &e : a) cin >> e;
int q; cin >> q;
while(q--){
int x; cin >> x;
int pos = upper_bound(all(a), x) - a.begin() - 1;
if(pos < 0){
cout << abs(a.back() - x);
}else if(pos >= n-1){
cout << abs(x - a[0]);
}else if(abs(a[pos+1] - x) >= abs(a[pos] - x)){
cout << abs(a[pos] - x) + solve(pos, pos, a[pos]);
}else{
cout << abs(a[pos+1] - x) + solve(pos+1, pos+1, a[pos+1]);
}
cout << '\n';
}
return 0;
}