Submission #1025414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025414		NoLove	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	348 KiB

bridge

/**
 *    author : Lăng Trọng Đạt
 *    created: 17-07-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;
int n, k, ans = 0;

vector<pii> p;

void sub1() {
    vector<int> other;
    pii phai, trai;
    vector<int> val;
    for (auto[a, b] : p) {
        phai.second += a;
        trai.second += b;
        other.push_back(b);
        val.push_back(a);
        val.push_back(b);
    }
    sort(all(other));
    sort(all(p));
    sort(all(val));
    // db(p)
    // db(other)
    int curr = INF, i = 0, j = 0;
    for (int a : val) {
        while (i < si(other) && other[i] <= a) {
            trai.second -= other[i];
            trai.first += other[i++];
        }
        while (j < si(p) && p[j].f <= a) {
            phai.first += p[j].f;
            phai.second -= p[j++].f;
        }

        mi(curr, (phai.second - a * (si(p) - j)) + ((j) * a - phai.first) + 
                 (trai.second - a * (si(other) - i)) + ((i) * a - trai.first));
        int hi = (phai.second - a * (si(p) - j)) + ((j) * a - phai.first) + 
                 (trai.second - a * (si(other) - i)) + ((i) * a - trai.first);
        // db(phai, trai, a, i, j, hi)
        // if (a == 4) {
        //     db(i, j)
        //     db((i + 1) * a - trai.first)
        //     db((trai.second - a * (si(other) - i - 1)))
        // }
    }

    ans += curr;
}

void sub4() {
    vector<int> val;
    int sum = 0, a = 0, b = 0;
    for (auto[a, b] : p) {
        val.push_back(a);
        val.push_back(b);
        sum += a + b;
    }
    sort(all(val));

    int n = si(val), curr = INF;
    for (int  i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int cur = 0;
            for (auto[a, b] : p) {
                cur += min(abs(a - val[i]) + abs(b - val[i]), abs(a - val[j]) + abs(b - val[j]));
            }
            mi(curr, cur);
        }

    }
    // db(n, val)
    // for (int i = 0; i < n; i++) {
    //     pii mid;
    //     b = sum - a;
    //     for (int j = i, pos = i; j < n; j++) {
    //         mid.second += val[j];
    //         b -= val[j];
    //         while (pos < j && val[pos] <= (val[i] + val[j]) / 2) {
    //             mid.first += val[pos];
    //             mid.second -= val[pos++];
    //         }

    //         int tmp = (val[i] * i - a) + (b - val[j] * (n - j - 1)) + 
    //                   (mid.first - val[i] * (pos - i)) + (val[j] * (j - pos + 1) - mid.second);

    //         mi(curr, tmp);
    //         // if (i == 2 && j == 5)
    //         if(tmp == 8) {
    //             db(i, val[i], a)
    //             db(j, val[j], b)
    //             db(mid, pos, tmp)
    //             db((val[i] * i - a), (b - val[j] * (n - j - 1)))
    //             db((mid.first - val[i] * (pos - i)), (val[j] * (j - pos + 1) - mid.second))
    //             return;
    //         }
    //             // db(i, j, a, b, mid, pos)
    //     }
    //     a += val[i];
    // }   

    ans += curr;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 

    cin >> k >> n;
    char a, b;
    int x, y;
    FOR(i, 1, n) {
        cin >> a >> x >> b >> y;
        if (x > y) swap(x, y);
        if (a == b) {
            ans += y - x;
        } else {
            p.push_back({x, y});
        }
    }

    ans += si(p); // must cross bridge

    if (k == 1) {
        sub1();
    } else {
        sub4();
    }
    cout << ans;
}

Compilation message (stderr)

bridge.cpp: In function 'void sub1()':
bridge.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto[a, b] : p) {
      |              ^
bridge.cpp:59:13: warning: unused variable 'hi' [-Wunused-variable]
   59 |         int hi = (phai.second - a * (si(p) - j)) + ((j) * a - phai.first) +
      |             ^~
bridge.cpp: In function 'void sub4()':
bridge.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto[a, b] : p) {
      |              ^
bridge.cpp:86:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |             for (auto[a, b] : p) {
      |                      ^
bridge.cpp:74:18: warning: unused variable 'a' [-Wunused-variable]
   74 |     int sum = 0, a = 0, b = 0;
      |                  ^
bridge.cpp:74:25: warning: unused variable 'b' [-Wunused-variable]
   74 |     int sum = 0, a = 0, b = 0;
      |                         ^
bridge.cpp: In function 'int32_t main()':
bridge.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
bridge.cpp:136:5: note: in expansion of macro 'FOR'
  136 |     FOR(i, 1, n) {
      |     ^~~
bridge.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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