Submission #1055123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055123		Adomas08	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	28 ms	5532 KiB

bridge

            #include <bits/stdc++.h>
     
            using namespace std;
            int k, n;
            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<int> j){
            j.erase(remove(j.begin(), j.end(), -1), j.end());
            sort (j.begin(), j.end());
            if (j.size() == 0) return 0;
            return (j[j.size() / 2] + j[j.size() / 2 - 1]) / 2;
            }
            int main(){
            long long ans = 0, dans = 0;
            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 {
                    dans++;
                    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(z);
                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, g, c;
                sort(v.begin(), v.end(), sorting);
                z.clear();
                for (int i = 0; i < n; i++){
                    z.push_back(v[i].first);
                    z.push_back(v[i].second);
                }
                vector <int>start(z.begin(), z.begin() + 2);
                vector <int>ends(z.begin() + 2, z.end());
                for (int N = 1; N <= n; N++){
                h = z;
                curans = dans;
                if (N != 1){
                    start.push_back(z[N * 2 -1]);
                    start.push_back(z[N * 2]);
                    ends.erase(ends.begin());
                    ends.erase(ends.begin());
                }
                f = findmedian(start);
                g = findmedian(ends);
                for (int i = 0; i < n; i++){
                    if ((f >= a[i*2] && f <= a[i*2+1]) || (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 (h[i*2] != -1){
                        if (f < a[i*2])  c = 2 * (a[i*2] - f);
                        else c = 2 * (f - a[i*2+1]);
                        if (g < a[i*2]) c = min(2 * (a[i*2] - g), c);
                        else c = min(2 * (g - a[i*2+1]), c);
                        curans += c;
                    }
            }
     
            ans = min(curans, ans);
                }
            }
            cout << ans;
            }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:72:27: warning: unused variable 'xans' [-Wunused-variable]
   72 |                 long long xans;
      |                           ^~~~

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