Submission #3589614

---

Source Code Expand

#include <bits/stdc++.h>

#define MAX_N 100000

using namespace std;

typedef long long lint;

const lint sqrInf = (1e18) - 1;

lint rez;

int n;
int v[(MAX_N << 1) + 1];
lint sum[(MAX_N << 1) + 1];

int a[MAX_N + 1];
int b[MAX_N + 1];

int cate(int i, int a, int b)
{
    //cout << "NUMARAM " << v[i] << " " << a << " " << b << "\n";

    if(v[i] < a)
        return i;

    if(v[i] >= a && v[i] < b)
        return i - 1;

    return i - 2;
}

lint cautBin(int a, int b)
{
    if(a > b)
        swap(a, b);

    int i = 0;
    int pas = 1 << 17;
    while(pas != 0)
    {
        if(i + pas <= (n << 1) && cate(i + pas, a, b) < n)
            i += pas;

        pas >>= 1;
    }

   // cout << "ELEM " << a << " SI " << b << "\n";
   // cout << "SUNTEM " << i + 1 << " AVEM " << cate(i + 1, a , b) << " SUMA " << sum[i + 1] << " SCAD " << a * (v[i + 1] >= a) << " " << b * (v[i + 1] >= b) << "\n";

    if(i < (n << 1) && cate(i + 1, a, b) == n)
    {
        return sum[i + 1] - a * (v[i + 1] >= a) - b * (v[i + 1] >= b);
    }

    return sqrInf;
}

int main()
{
    cin >> n;

    int i;
    int k = 0;
    lint sa = 0, sb = 0;
    for(i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        v[++ k] = a[i];
        v[++ k] = b[i];

        sa += a[i];
        sb += b[i];
    }

    sort(v + 1, v + k + 1);
    for(int i = 1; i <= k; i ++)
    {
        sum[i] = sum[i - 1] + v[i];
       // cout << v[i] << " ";
    }
   // cout << "\n";

    rez = min(sa, sb);

    for(i = 1; i <= n; i ++)
        rez = min(rez, cautBin(a[i], b[i]));

    cout << rez << "\n";

    return 0;
}

Submission Info

Judge Result