Submission #1054195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054195		Mokocraft	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	59 ms	2100 KiB

bridge

#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <vector>
#include <cmath>

int main()
{
    //freopen("duotaA.txt", "r", stdin);

    int K, N;
    std::cin >> K >> N;

    long long extra = 0;
    std::vector<std::pair<int, int>> ranges;
    for(int i = 0; i < N; i++)
    {
        int ai, bi;
        char ac, bc;
        std::cin >> ac >> ai >> bc >> bi;

        if(ai > bi)
            std::swap(ai, bi);

        if(ac == bc)
            extra += bi - ai;
        else
            ranges.push_back(std::make_pair(ai, bi));
    }

    N = ranges.size();

    if(N == 0)
    {
        std::cout << extra;
        return 0;
    }

    if(K == 1)
    {
        long long dist = 0;
        int nums[N*2];
        for(int i = 0; i < N; i++)
        {
            nums[i*2] = ranges[i].first;
            nums[i*2+1] = ranges[i].second;
        }

        std::sort(nums, nums + N*2);

        int point = nums[N];

        for(int i = 0; i < N; i++)
        {
            if(point >= ranges[i].first && point <= ranges[i].second)
                dist += 1 + ranges[i].second - ranges[i].first;
            else dist += 1 + ranges[i].second - ranges[i].first + 2 * std::min(std::abs(ranges[i].second - point), std::abs(ranges[i].first - point));
        }

        std::cout << dist + extra;
    }
    else
    {
        // speju kad gali buti po puses masyvu mediana jeigu K == 2

        long long dist = 0;
        int nums[N*2];
        for(int i = 0; i < N; i++)
        {
            nums[i*2] = ranges[i].first;
            nums[i*2+1] = ranges[i].second;
        }

        std::sort(nums, nums + N*2);

        int point1, point2;
        point1 = nums[N/2];
        point2 = nums[N/2 + N];

        for(int i = 0; i < N; i++)
        {
            int temp1;
            int temp2;

            if(point1 >= ranges[i].first && point1 <= ranges[i].second)
                temp1 = 1 + ranges[i].second - ranges[i].first;
            else temp1 = 1 + ranges[i].second - ranges[i].first + 2 * std::min(std::abs(ranges[i].second - point1), std::abs(ranges[i].first - point1));

            if(point2 >= ranges[i].first && point2 <= ranges[i].second)
                temp2 = 1 + ranges[i].second - ranges[i].first;
            else temp2 = 1 + ranges[i].second - ranges[i].first + 2 * std::min(std::abs(ranges[i].second - point2), std::abs(ranges[i].first - point2));

            dist += std::min(temp1, temp2);
        }

        std::cout << dist + extra;
    }

    return 0;
}

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