Submission #1055021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055021		Adomas08	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	604 KiB

bridge

    #include <bits/stdc++.h>

    using namespace std;
    int k, n;
    int p, o;
    long long curans;
    vector <int> h;
    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;
    int k, n;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k >> n;
    vector <int> z;
    vector <pair<int,int>> v;
    char b, d;
    for (int i = 0; i < n; i++){
        cin >> b >> p >> d >> o;
        if (b == d){
            v.push_back({-1, -1});
            z.push_back(-1);
            z.push_back(-1);
        }
        else {
            dans++;
            v.push_back({min(p, o), max(p, o)});
            z.push_back(p);
            z.push_back(o);
        }
        dans += abs(o - p);
    }
    int f;
    if (k == 1){
    while (k--){
        ans = dans;
        f = findmedian(v);
        for (int i = 0; i < n; i++){
            if (f >= v[i].first && f <= v[i].second){
                v[i].first = -1;
                v[i].second = -1;
            }
        }
    }
    for (int i = 0; i < n; i++){
                if (v[i].first != -1 && h[i*2] != -1){
                if (f < v[i].first) ans += 1 + v[i].second - v[i].first + 2 * (v[i].first - f);
                if (f > v[i].second) ans += 1 + v[i].second - v[i].first + 2 * (f - v[i].second);
            }
        }
    }
    else{
        ans = LLONG_MAX;
        long long xans;
        int f, g, 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++){
        h = z;
        curans = dans;
        if (N != 1){
            start.push_back(v[N-1]);
            ends.erase(ends.begin());
        }
        f = findmedian(start);
        g = findmedian(ends);
        for (int i = 0; i < n; i++){
            if ((f >= v[i].first && f <= v[i].second) || (g >= v[i].first && g <= v[i].second)){
                h[i*2] = -1;
                h[i*2+1] = -1;
            }
        }
        for (int i = 0; i < n; i++){
        if (v[i].first != -1 && h[i*2] != -1){
                if (f < v[i].first)  c = 2 * (v[i].first- f);
                else c = 2 * (f - v[i].second);
                if (g < v[i].first) c = min(2 * (v[i].first - g), c);
                else c = min(2 * (g - v[i].second), 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:13: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]
   13 |     for (int i = 0; i < j.size(); i++){
      |                     ~~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:67:19: warning: unused variable 'xans' [-Wunused-variable]
   67 |         long long xans;
      |                   ^~~~

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