Submission #794622

#	Time	Username	Problem	Language	Result	Execution time	Memory
794622		vjudge1	Bitaro's travel (JOI23_travel)	C++17	0 / 100	83 ms	2784 KiB

travel

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const int N = 200200;

int a[N];

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q, s, l, r, m, ll, rr, ans, cr;
    cin >> n;
    for(int i = 0; i < n; ++ i) {
        cin >> a[i];
    }
    for(cin >> q; q --> 0;) {
        cin >> s;
        ll = -1, rr = n; // a[l] <= s < a[r];
        for(; ll + 1 < rr;) {
            m = (ll + rr) / 2;
            (s < a[m] ? rr : ll) = m;
        }
        cr = (ll == -1 || (rr < n && a[rr] - s < s - a[ll]) ? rr : ll);
        ans = abs(a[cr] - s);
        for(; ll > -1 && rr < n;) {
            if(a[rr] - a[cr] < a[cr] - a[ll]) {
                l = rr, r = n;
                for(; l + 1 < r;) {
                    m = (l + r) / 2;
                    (a[m] - a[m - 1] < a[m - 1] - a[ll] ? l : r) = m;
                }
                ans += a[l] - a[cr];
                cr = l;
                rr = l + 1;
            } else {
                l = -1, r = ll;
                for(; l + 1 < r;) {
                    m = (l + r) / 2;
                    (a[rr] - a[m + 1] < a[m + 1] - a[m] ? l : r) = m;
                }
                ans += a[cr] - a[r];
                cr = r;
                ll = r - 1;
            }
        }
        if(ll < 0 && rr < n) {
            ans += a[n - 1] - a[cr];
        } else if(rr >= n && ll > -1) {
            ans += a[cr] - a[0];
        } 
        cout << ans << '\n';
    }
}

Compilation message (stderr)

travel.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main() {
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55