Submission #1054999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054999		Adomas08	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2031 ms	7968 KiB

bridge

    #include <bits/stdc++.h>

    using namespace std;
    int k, n;
    bool sorting(pair <int, int> a, pair <int, int> b){
    return a.first + a.second < b.first + b.second;
    }
    int findmedian(vector<pair<int, int>> j){
    vector <int> d;
    for (int i = 0; i < j.size(); i++){
        d.push_back(j[i].first);
        d.push_back(j[i].second);
    }
    d.erase(remove(d.begin(), d.end(), -1), d.end());
    sort (d.begin(), d.end());
    if (d.size() == 0) return 0;
    return (d[d.size() / 2] + d[d.size() / 2 - 1]) / 2;
    }
    int main(){
    long long ans = 0, dans = 0;
    priority_queue <int> q;
    int k, n;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> k >> n;
    int a[n*2];
    vector <int> z;
    vector <pair<int,int>> v;
    char b[n], d[n];
    for (int i = 0; i < n; i++){
        cin >> b[i] >> a[i*2] >> d[i] >> a[i*2+1];
        if (b[i] == d[i]){
            v.push_back({-1, -1});
            z.push_back(-1);
            z.push_back(-1);
        }
        else {
            v.push_back({a[i*2], a[i*2+1]});
            z.push_back(a[i*2]);
            z.push_back(a[i*2+1]);
        }
        if (a[i*2] > a[i*2+1]){
            swap(a[i*2], a[i*2+1]);
        }
        dans += a[i*2+1] - a[i*2];
    }
    int f;
    if (k == 1){
    while (k--){
        f = findmedian(v);
        for (int i = 0; i < n; i++){
            if (f >= a[i*2] && f <= a[i*2+1]){
                v[i].first = -1;
                v[i].second = -1;
            }
        }
    }
    for (int i = 0; i < n; i++){
        if (b[i] == d[i]){
            ans += a[i*2+1] - a[i*2];
        }
        else{
            if (v[i].first == -1){
                ans += a[i*2+1] - a[i*2] + 1;
            }
            else{
                if (f < a[i*2]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f);
                if (f > a[i*2+1]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]);
            }
        }
    }
    }
    else{
        ans = LLONG_MAX;
        long long xans;
        int f = -1, g = -1, af, ag, c;
        sort(v.begin(), v.end(), sorting);
        vector <pair<int, int>>start(v.begin(), v.begin() + 1);
        vector <pair<int, int>>ends(v.begin() + 1, v.end());
        for (int N = 1; N <= n; N++){
        if (f != -1){
            af = f;
            ag = g;
        }
        vector <int> h = z;
        long long curans = dans;
        if (N != 1){
            start.push_back(v[N-1]);
            ends.erase(ends.begin());
        }
        f = findmedian(start);
        g = findmedian(ends);
        if (af != f || ag != g){
        for (int i = 0; i < n; i++){
            if (f >= a[i*2] && f <= a[i*2+1]){
                h[i*2] = -1;
                h[i*2+1] = -1;
            }
        }
        for (int i = 0; i < n; i++){
            if (g >= a[i*2] && g <= a[i*2+1]){
                h[i*2] = -1;
                h[i*2+1] = -1;
            }
        }
        for (int i = 0; i < n; i++){
        if (b[i] != d[i]){
            if (h[i*2] == -1){
                curans +=  1;
            }
            else{
                if (f < a[i*2])  c = 1 + 2 * (a[i*2] - f);
                else c = 1 + 2 * (f - a[i*2+1]);
                if (g < a[i*2]) c = min(1 + 2 * (a[i*2] - g), c);
                else c = min(1 + 2 * (g - a[i*2+1]), c);
                curans += c;
            }
        }
    }

    ans = min(curans, ans);
        }
        }
    }
    cout << ans;
    }

Compilation message (stderr)

bridge.cpp: In function 'int findmedian(std::vector<std::pair<int, int> >)':
bridge.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < j.size(); i++){
      |                     ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:75:19: warning: unused variable 'xans' [-Wunused-variable]
   75 |         long long xans;
      |                   ^~~~
bridge.cpp:93:27: warning: 'ag' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         if (af != f || ag != g){
      |                        ~~~^~~~
bridge.cpp:93:16: warning: 'af' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         if (af != f || ag != g){
      |             ~~~^~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37