Submission #1233887

#TimeUsernameProblemLanguageResultExecution timeMemory
1233887nasjesBest Place (NOI17_bestplace)C++20
100 / 100
62 ms3488 KiB
#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];

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 nw=x[i]*i-prx[i];
         nw+=(prx[n]-prx[i])-(n-i)*x[i];
      //   cout<<nw<<endl;
         if(nw<ans){
             ans=nw;
             x0=x[i];
         }
    }


    ans=inf;

    for(int i=1; i<=n; i++){
        ll nw=y[i]*i-pry[i];
        nw+=(pry[n]-pry[i])-(n-i)*y[i];
        if(nw<ans){
            ans=nw;
            y0=y[i];
        }
    }
    cout<<x0<<" "<<y0<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...