oj.uz

Submission #794619

# Submission time Handle Problem Language Result Execution time Memory
794619 2023-07-26T16:53:51 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 92 ms 6088 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 81 ms 4952 KB Output is correct
8 Correct 77 ms 4992 KB Output is correct
9 Correct 79 ms 5016 KB Output is correct
10 Correct 78 ms 4972 KB Output is correct
11 Correct 92 ms 4964 KB Output is correct
12 Correct 81 ms 4924 KB Output is correct
13 Correct 32 ms 4180 KB Output is correct
14 Correct 23 ms 1484 KB Output is correct
15 Incorrect 67 ms 6088 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -