Submission #3050589

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll solve(int N, vi& x, vi& y) {
    if (N == 1) return 0;

    vector<ii> xy(N*2);
    rep(i,N) {
        xy[i*2] = ii(x[i], i);
        xy[i*2+1] = ii(y[i], i);
    }
    sort(ALL(xy));

    ll best = LLONG_MAX;
    {
        int amin = xy[0].first, bmax = xy.back().first;
        int amin_at = xy[0].second, bmax_at = xy.back().second;

        int amax = min(x[bmax_at], y[bmax_at]),
            bmin = max(x[amin_at], y[amin_at]);

        rep(i,N) {
            if (i == amin_at || i == bmax_at) continue;
            amax = max(amax, min(x[i], y[i]));
            bmin = min(bmin, max(x[i], y[i]));
        }

        ll da = amax - amin, db = bmax - bmin;
        best = min(best, da * db);
    }
    {
        int amin = xy[0].first, amax = xy.back().first;
        int amin_at = xy[0].second, amax_at = xy.back().second;
        ll da = amax - amin;
        if (amin_at != amax_at) {
            int bmin = max(x[amin_at], y[amin_at]),
                bmax = min(x[amax_at], y[amax_at]);
            if (bmin > bmax) swap(bmin, bmax);

            vector<ii> smaller;
            smaller.reserve(N-2);

            rep(i,N) {
                if (i == amin_at || i == amax_at) continue;
                smaller.pb(ii(min(x[i], y[i]), i));
            }
            sort(ALL(smaller));

            int rmin = bmin, rmax = bmax;
            rep(j,N-2) {
                int wmin = smaller[j].first;
                int wmax = smaller.back().first;
                ll db = max(rmax, wmax) - min(rmin, wmin);
                best = min(best, da * db);

                int i = smaller[j].second;
                int larger = max(x[i], y[i]);
                rmin = min(rmin, larger);
                rmax = max(rmax, larger);
            }
            ll db = rmax - rmin;
            best = min(best, da * db);
        }
    }

    return best;
}

int main() {
    int N;
    scanf("%d", &N);
    vi x(N), y(N);
    rep(i,N){
        scanf("%d %d", &x[i], &y[i]);
    }
    cout << solve(N,x,y) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Ball Coloring
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3321 Byte
Status
Exec Time 103 ms
Memory 6528 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:113:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x[i], &y[i]);
                                     ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2
All 700 / 700 div20, div21, div22, div23, div24, example0, example1, example2, maxrand0, maxrand1, maxrand2, maxrand20, maxrand21, maxrand210, maxrand211, maxrand22, maxrand23, maxrand24, maxrand25, maxrand26, maxrand27, maxrand28, maxrand29, maxrand3, maxrand4, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, sparse0, sparse1, sparse2, sparse3, sparse4
Case Name Status Exec Time Memory
div20 92 ms 6528 KB
div21 93 ms 6528 KB
div22 92 ms 6528 KB
div23 93 ms 6528 KB
div24 93 ms 6528 KB
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
maxrand0 92 ms 6528 KB
maxrand1 92 ms 6528 KB
maxrand2 93 ms 6528 KB
maxrand20 98 ms 6528 KB
maxrand21 98 ms 6528 KB
maxrand210 89 ms 6528 KB
maxrand211 98 ms 6528 KB
maxrand22 99 ms 6528 KB
maxrand23 98 ms 6528 KB
maxrand24 96 ms 6528 KB
maxrand25 97 ms 6528 KB
maxrand26 98 ms 6528 KB
maxrand27 98 ms 6528 KB
maxrand28 97 ms 6528 KB
maxrand29 95 ms 6528 KB
maxrand3 94 ms 6528 KB
maxrand4 93 ms 6528 KB
smallrand0 1 ms 256 KB
smallrand1 1 ms 256 KB
smallrand2 1 ms 256 KB
smallrand3 1 ms 256 KB
smallrand4 1 ms 256 KB
sparse0 103 ms 6528 KB
sparse1 103 ms 6528 KB
sparse2 102 ms 6528 KB
sparse3 103 ms 6528 KB
sparse4 102 ms 6528 KB