Submission #1233880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233880		nasjes	Best Place (NOI17_bestplace)	C++20	3 / 100	61 ms	3400 KiB

bestplace

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6 + 10;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, a[dim];
pll pnt[dim];
ll x[dim], y[dim];
ll prx[dim], pry[dim];
ll last(ll val){
    ll l=1;
    ll r=n;
    while(r-l>=1){
        ll mid=(l+r+1)/2;
        if(a[mid]<=val){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    return l;


}

int main() {
    cin>>n;
    for(int  i=1; i<=n; i++){
        cin>>x[i]>>y[i];
    }
    sort(x+1, x+1+n);
    sort(y+1, y+1+n);
    for(int i=1; i<=n;i++){
        prx[i]=prx[i-1]+x[i];
        pry[i]=pry[i-1]+y[i];

    }
    ll x0, y0;
    x0=1;
    y0=1;
    ll ans=inf;
    for(int i=1; i<=n; i++){
        ll cur=last(y[i]);
        ll nw=x[i]*cur-prx[cur];
         nw+=(prx[n]-prx[cur])-(n-cur)*x[i];
         if(nw<ans){
             ans=nw;
             x0=x[i];
         }
    }


    ans=inf;
    for(int i=1; i<=n; i++){
        ll cur=last(y[i]);
        ll nw=y[i]*cur-pry[cur];
        nw+=(pry[n]-pry[cur])-(n-cur)*y[i];
        if(nw<ans){
            ans=nw;
            y0=y[i];
        }
    }
    cout<<x0<<" "<<y0<<endl;
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 20
• Subtask 3: 0 / 28
• Subtask 4: 0 / 13
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19