제출 #414866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414866		blue	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	121 ms	2860 KiB

bridge

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;

struct path
{
    long long a;
    long long b;
};

bool operator < (path X, path Y)
{
    return X.a + X.b < Y.a + Y.b;
};

int main()
{

    int K, N;
    cin >> K >> N;

    if(K == 1)
    {
        long long res = 0;
        char c1, c2;
        long long e1, e2;
        vector<long long> A;
        for(int i = 1; i <= N; i++)
        {
            cin >> c1 >> e1 >> c2 >> e2;

            if(c1 == c2) res += abs(e1 - e2);
            else
            {
                A.push_back(e1);
                A.push_back(e2);
                res += 1;
            }
        }
        sort(A.begin(), A.end());
        for(int i = 0; i < A.size(); i++) res += abs(A[i] - A[A.size()/2]);

        cout << res << '\n';
        return 0;
    }
    else
    {
        long long res = 0;
        vector<path> P;

        long long basic = 0;

        for(int i = 1; i <= N; i++)
        {
            char c1, c2;
            int e1, e2;
            cin >> c1 >> e1 >> c2 >> e2;


            if(c1 == c2)
            {
                basic += abs(e1 - e2);
            }
            else
            {
                basic++;
                if(e1 > e2) swap(e1, e2);
                P.push_back(path{e1, e2});
            }
        }

        sort(P.begin(), P.end());
        // for(path p:P) cerr << p.a << ' ' << p.b << '\n';


        multiset<long long> left_low, left_high, right_low, right_high;
        long long left_low_sum = 0, left_high_sum = 0, right_low_sum = 0, right_high_sum = 0;



        // cerr << "\n\n\n";
        //initially, everything is in right

        for(path p:P)
        {
            right_high.insert(p.a);
            right_high_sum += p.a;

            right_high.insert(p.b);
            right_high_sum += p.b;
        }

        while(right_high.size() > right_low.size())
        {
            int x = *right_high.begin();

            right_high.erase(right_high.begin());
            right_high_sum -= x;

            right_low.insert(x);
            right_low_sum += x;
        }

        // for(int x: right_low) cerr << x << ' ';
        // cerr << '\n';
        // for(int x: right_high) cerr << x << ' ';
        // cerr << '\n';

        res = right_high_sum - right_low_sum;

        // for(int uv: left_low) cerr << uv << ' ';
        // cerr << '\n';
        // for(int uv: left_high) cerr << uv << ' ';
        // cerr << '\n';
        // for(int uv: right_low) cerr << uv << ' ';
        // cerr << '\n';
        // for(int uv: right_high) cerr << uv << ' ';
        // cerr << '\n';
        //
        // cerr << "\n\n\n";
        //
        // cerr << res << '\n';

        for(path p:P)
        {
            for(int val: {p.a, p.b})
            {
                if(right_high.find(val) != right_high.end())
                {
                    right_high.erase(val);
                    right_high_sum -= val;
                }
                else
                {
                    right_low.erase(val);
                    right_low_sum -= val;
                }

            }


            while(right_high.size() > right_low.size())
            {
                int x = *right_high.begin();

                right_high.erase(right_high.begin());
                right_high_sum -= x;

                right_low.insert(x);
                right_low_sum += x;
            }

            while(right_low.size() > right_high.size())
            {
                int x = *right_low.rbegin();

                right_low.erase(right_low.find(*right_low.rbegin()));
                right_low_sum -= x;

                right_high.insert(x);
                right_high_sum += x;
            }












            left_high.insert(p.a);
            left_high_sum += p.a;

            left_high.insert(p.b);
            left_high_sum += p.b;

            while(left_high.size() > left_low.size())
            {
                int x = *left_high.begin();

                left_high.erase(left_high.begin());
                left_high_sum -= x;

                left_low.insert(x);
                left_low_sum += x;
            }







            // for(int uv: left_low) cerr << uv << ' ';
            // cerr << '\n';
            // for(int uv: left_high) cerr << uv << ' ';
            // cerr << '\n';
            // for(int uv: right_low) cerr << uv << ' ';
            // cerr << '\n';
            // for(int uv: right_high) cerr << uv << ' ';
            // cerr << '\n';
            // cerr << "sum = " << left_high_sum - left_low_sum  << ' ' <<  right_high_sum - right_low_sum << '\n';
            //
            // cerr << "\n\n\n";







            res = min(res, left_high_sum - left_low_sum  +  right_high_sum - right_low_sum);
        }

        res += basic;
        cout << res << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < A.size(); i++) res += abs(A[i] - A[A.size()/2]);
      |                        ~~^~~~~~~~~~

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