Submission #40737

#	Time	Username	Problem	Language	Result	Execution time	Memory
40737		bogdan10bos	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	64 ms	1772 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;
typedef pair<int, int> pii;

namespace solve1
{
    int N;
    LL ans;
    vector<pii> v;

    LL getCost(int pos)
    {
        LL ans = 0;
        for(auto x: v)
            ans += abs(pos - x.first) + abs(pos - x.second);
        return ans;
    }

    void solve()
    {
        scanf("%d\n", &N);
        for(int i = 1; i <= N; i++)
        {
            char c1, c2;
            int x, y;
            scanf("%c %d %c %d\n", &c1, &x, &c2, &y);
            if(c1 == c2)    ans += abs(x - y);
            else
                v.push_back({x, y}), ans++;
        }

        int p = 0, u = 1e9;
        while(p < u)
        {
            int mij1 = p + (u - p) / 2;
            int mij2 = p + (u - p) / 2 + 1;

            LL cost1 = getCost(mij1);
            LL cost2 = getCost(mij2);

            if(cost1 < cost2)   u = mij1;
            else p = mij2;
        }
        ans += min(getCost(p), getCost(u));
        printf("%lld\n", ans);
    }
}

namespace solve2
{
    int N;
    LL ans;
    vector<pii> v;

    LL getCost(LL a, LL b)
    {
        LL ans = 0;
        for(auto x: v)
            ans += min( abs(a - x.first) + abs(a - x.second) ,
                        abs(b - x.first) + abs(b - x.second) );
        return ans;
    }

    LL ternary2(LL x, LL st, LL dr)
    {
        if(st == dr)    return getCost(x, st);

        LL mij1 = st + (dr - st) / 2;
        LL mij2 = st + (dr - st) / 2 + 1;

        LL c1 = getCost(x, mij1);
        LL c2 = getCost(x, mij2);

        if(c1 < c2) return ternary2(x, st, mij1);
        return ternary2(x, mij2, dr);
    }

    LL ternary1(LL st, LL dr)
    {
        if(st == dr)    return ternary2(st, st + 1, int(1e9));

        LL mij1 = st + (dr - st) / 2;
        LL mij2 = st + (dr - st) / 2 + 1;

        LL c1 = ternary2(mij1, mij1 + 1, int(1e9));
        LL c2 = ternary2(mij2, mij2 + 1, int(1e9));

        if(c1 < c2) return ternary1(st, mij1);
        return ternary1(mij2, dr);
    }

    void solve()
    {
        scanf("%d\n", &N);
        for(int i = 1; i <= N; i++)
        {
            char c1, c2;
            int x, y;
            scanf("%c %d %c %d\n", &c1, &x, &c2, &y);
            if(c1 == c2)    ans += abs(x - y);
            else
                v.push_back({x, y}), ans++;
        }

        ans += ternary1(0, int(1e9) - 1);
        printf("%lld\n", ans);
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    int K;
    scanf("%d", &K);
    if(K == 1)
        solve1::solve();
    else
        solve2::solve();

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void solve1::solve()':
bridge.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d\n", &N);
                          ^
bridge.cpp:31:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c %d %c %d\n", &c1, &x, &c2, &y);
                                                     ^
bridge.cpp: In function 'void solve2::solve()':
bridge.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d\n", &N);
                          ^
bridge.cpp:104:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c %d %c %d\n", &c1, &x, &c2, &y);
                                                     ^
bridge.cpp: In function 'int main()':
bridge.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &K);
                    ^

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