Submission #590712

#	Time	Username	Problem	Language	Result	Execution time	Memory
590712		Vanilla	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	300 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
typedef long long int64;
using namespace std;
const int maxn = 3e3 + 2;
int64 pref[maxn];
 
struct way {
    int64 l, r, cost;
};
 
long long find_shortcut(int n, vector<int> l, vector<int> d, int c){
    vector <way> a;
    for (int i = 0; i < n - 1; i++){
        pref[i] = l[i] + (i ? pref[i-1]: 0);
    }
    auto query = [] (int l, int r) -> int64 {
        if (l > r) swap(l, r);
        if (r == 0 || l == r) return 0;
        return pref[r-1] - (l - 1 == -1 ? 0: pref[l-1]);
    };
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            a.push_back({i, j, d[i] + d[j] + query(i, j)});
        }
    }
    sort(a.begin(), a.end(), [] (way &a, way &b) {
        if (a.cost != b.cost) return a.cost > b.cost;
        if (a.l != b.l) return a.l < b.l;
        return a.r < b.r;
    });
    // for (auto i: a){
    //     cout << i.l << " " << i.r << " " << i.cost << "\n";
    // }
    auto add = [&] (int l, int r) -> int64 {
        int64 diam = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                diam = max(diam, (int64) d[i] + d[j] + min(query(i, j), query(i, l) + c + query(r, j)));
            }
        }
        return diam;
    };
    auto check = [&] (int64 x) -> bool {
        int64 mxl = 0, mnr = 0;
        for (int i = 0; i < a.size(); i++){
            if (a[i].cost <= x) break;
            mxl = max(mxl, a[i].l);
            mnr = max(mnr, a[i].r);
        }
        // cout << mxl << " " << mnr << " " << x << "\n";
        if (mnr == 1e9) return 1;
        if (mxl > mnr) return 0;
        return add(mxl, mnr) <= x;
    };
    int64 il = 0, ir = 1e15, rs = -1;
    while (il <= ir) {
        int64 mid = (il + ir) / 2;
        if (check(mid)) {
            rs = mid;
            ir = mid - 1;
        }
        else {
            il = mid + 1;
        }
    }
    
    // int64 rs = 1e18;
    // for (int i = 0; i < n; i++){
    //     for (int j = i + 1; j < n; j++){
    //         // cout << i << " " << j << " " << add(i,j) << "\n";
    //         rs = min(rs, add(i, j));
    //     }
    // }
    return rs;
}

Compilation message (stderr)

shortcut.cpp: In lambda function:
shortcut.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<way>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 0; i < a.size(); i++){
      |                         ~~^~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3