oj.uz

Submission #40737

# Submission time Handle Problem Language Result Execution time Memory
40737 2018-02-07T18:22:03 Z bogdan10bos Palembang Bridges (APIO15_bridge) C++14
22 / 100
 64 ms 1772 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 1 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 38 ms 1772 KB Output is correct
13 Correct 56 ms 1772 KB Output is correct
14 Correct 40 ms 1772 KB Output is correct
15 Correct 33 ms 1772 KB Output is correct
16 Correct 43 ms 1772 KB Output is correct
17 Correct 52 ms 1772 KB Output is correct
18 Correct 52 ms 1772 KB Output is correct
19 Correct 64 ms 1772 KB Output is correct
20 Correct 62 ms 1772 KB Output is correct
21 Correct 51 ms 1772 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Incorrect 4 ms 1772 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Incorrect 3 ms 1772 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Incorrect 3 ms 1772 KB Output isn't correct
4 Halted 0 ms 0 KB -