Submission #399373

#	Time	Username	Problem	Language	Result	Execution time	Memory
399373		model_code	Izvanzemaljci (COI21_izvanzemaljci)	C++17	100 / 100	1386 ms	17784 KiB

izvanzemaljci

#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second


using namespace std;

typedef long long ll;

const int MAXN = 100005;
const ll INF = 200000000011;
typedef pair<ll,ll> ii;

int n,k;
ii p[MAXN];


struct AABB{
    bool inited;
    ii a, b;
    AABB(){
        inited = false;
    }
    AABB(ii x){
        a = x;
        b = x;
        inited = true;
    }
    void rotate90(){
        ii na = ii(min(-a.Y, -b.Y), min(a.X, b.X));
        ii nb = ii(max(-a.Y, -b.Y), max(a.X, b.X));
        a=na;b=nb;
    }
    void add_ii(ii x){
        if(!inited){
            a = x;
            b = x;
            inited = true;
        }
        a.X = min(a.X, x.X);
        a.Y = min(a.Y, x.Y);
        b.X = max(b.X, x.X);
        b.Y = max(b.Y, x.Y);
    }
    void expand_left(ll amt){
        a.X -= amt;
    }
    void expand_right(ll amt){
        b.X += amt;
    }
    void expand_down(ll amt){
        a.Y -= amt;
    }
    void expand_up(ll amt){
        b.Y += amt;
    }
    ll width(){
        return b.X-a.X;
    }
    ll height(){
        return b.Y-a.Y;
    }
    ll max_dim(){
        return max(width(), height());
    }
    bool contains(ii p){
        return (a.X<=p.X && p.X<=b.X
             && a.Y<=p.Y && p.Y<=b.Y);
    }
    bool overlaps(AABB d){
        return contains(d.a) || contains(d.b)
            || contains(ii(d.a.X, d.b.Y)) || contains(ii(d.b.X, d.a.Y))
            || d.contains(a) || d.contains(b)
            || d.contains(ii(a.X, b.Y)) || d.contains(ii(b.X, a.Y));
    }
};

void rotate90(ll n, ii* p){
    for(int i=0;i<n;i++){
        ii old = p[i];
        p[i] = ii(-old.Y, old.X);
    }
}

bool cmp(ii a, ii b){
    if(a.Y==b.Y) return a.X<b.X;
    return a.Y<b.Y;
}

ll solve1(int n, ii* p, vector<AABB>& sol){
    AABB aabb;
    for(int i=0;i<n;i++){
        aabb.add_ii(p[i]);
    }
    if(aabb.max_dim()==0) aabb.expand_left(1);
    aabb.expand_left(aabb.max_dim() - aabb.width());
    aabb.expand_down(aabb.max_dim() - aabb.height());
    sol.push_back(aabb);
    return aabb.max_dim();
}


ll dp[MAXN];
vector<AABB> dp2[MAXN];
void prepare_dp(){
    fill(dp, dp+MAXN, -1);
    for(int i=0;i<MAXN;i++) dp2[i].clear();
}
ll solve2(int n, ii* p, vector<AABB>& sol, ll x0=-INF){
    if(dp[n]==-1){
        ll& sol1 = dp[n];
        vector<AABB>& sol2 = dp2[n];
        if(n==0){
            AABB k1(ii(x0+5,x0+5));
            k1.expand_left(1);
            k1.expand_down(1);
            AABB k2(ii(x0+10, x0+10));
            k2.expand_right(1);
            k2.expand_down(1);
            sol1=1;
            sol2.push_back(k1);
            sol2.push_back(k2);
        }else if(n==1){
            AABB k1(p[0]);
            k1.expand_left(1);
            k1.expand_down(1);
            AABB k2(ii(p[0].X +10, p[0].X +10));
            k2.expand_right(1);
            k2.expand_down(1);
            sol1=1;
            sol2.push_back(k1);
            sol2.push_back(k2);
        }else{
            sol1 = INF;

            vector<AABB> aabb1, aabb2;
            // Uzduz x-osi su -> provjeri prignjecenost srednjeg
            sort(p, p+n);
            aabb1.push_back(AABB(p[0]));
            for(int i=1;i<n;i++){
                AABB nxt = aabb1.back();
                nxt.add_ii(p[i]);
                aabb1.push_back(nxt);
            }
            aabb1[0].expand_left(1);
            aabb2.push_back(AABB(p[n-1]));
            for(int i=n-2;i>=0;i--){
                AABB nxt = aabb2.back();
                nxt.add_ii(p[i]);
                aabb2.push_back(nxt);
            }
            aabb2[0].expand_right(1);
            for(int i=0;i<n-1;i++){
                AABB k1 = aabb1[i];
                AABB k2 = aabb2[n-i-2];
                k1.expand_left(min(k1.max_dim() - k1.width(), k1.a.X-x0-1));
                k1.expand_right(k1.max_dim() - k1.width());
                k1.expand_down(k1.max_dim() - k1.height());
                k2.expand_right(k2.max_dim() - k2.width());
                k2.expand_down(k2.max_dim() - k2.height());


                if(!k1.overlaps(k2)){
                    ll csol1 = max(k1.max_dim(), k2.max_dim());
                    if(csol1 < sol1){
                        sol1 = csol1;
                        sol2.clear();
                        sol2.push_back(k1);
                        sol2.push_back(k2);
                    }
                }
            }
            // Uzduz y-osi su -> mogu rasti kako zele
            sort(p, p+n, cmp);
            aabb1.clear();aabb2.clear();

            aabb1.push_back(AABB(p[0]));
            for(int i=1;i<n;i++){
                AABB nxt = aabb1.back();
                nxt.add_ii(p[i]);
                aabb1.push_back(nxt);
            }
            aabb1[0].expand_down(1);

            aabb2.push_back(AABB(p[n-1]));
            for(int i=n-2;i>=0;i--){
                AABB nxt = aabb2.back();
                nxt.add_ii(p[i]);
                aabb2.push_back(nxt);
            }
            aabb2[0].expand_up(1);

            for(int i=0;i<n-1;i++){
                AABB prvi = aabb1[i];
                AABB drugi = aabb2[n-i-2];
                if(!prvi.overlaps(drugi)){
                    ll csol1 = max(prvi.max_dim(), drugi.max_dim());
                    if(csol1 < sol1){
                        sol1 = csol1;
                        sol2.clear();
                        AABB k1 = prvi, k2 = drugi;
                        k1.expand_right(k1.max_dim() - k1.width());
                        k1.expand_down(k1.max_dim() - k1.height());
                        k2.expand_right(k2.max_dim() - k2.width());
                        k2.expand_up(k2.max_dim() - k2.height());
                        sol2.push_back(k1);
                        sol2.push_back(k2);
                    }
                }
            }
        }
    }
    sol.insert(sol.end(), dp2[n].begin(), dp2[n].end());
    return dp[n];
}

bool possible(int n, ii* p, ll d, vector<AABB>& sol){
    sort(p, p+n);
    AABB aabb;
    int i,j;
    for(i=0,j=0;i<n;i=j){
        AABB nxt = aabb;
        for(;j<n;j++){
            if(p[j].X == p[i].X){
                nxt.add_ii(p[j]);
            }else{
                break;
            }
        }
        if(nxt.max_dim() > d) break;
        else aabb = nxt;
    }
    if(!aabb.inited) return false;
    if(aabb.max_dim()==0) aabb.expand_left(1);
    aabb.expand_left(aabb.max_dim()-aabb.width());
    aabb.expand_down(aabb.max_dim()-aabb.height());
    sol.push_back(aabb);
    return solve2(n-i, p+i, sol, aabb.b.X)<=d;
}

int solve3(int n, ii* p, vector<AABB>& sol){
    if(n<=2){
        solve2(n, p, sol);
        AABB k3(ii(p[0].X +20, p[0].X +20));
        k3.expand_right(1);
        k3.expand_down(1);
        sol.push_back(k3);
        return 1;
    }
    ll sol1 = INF;
    for(int i=0;i<4;i++){
        vector<AABB> tmp;
        ll lo = 1, hi = INF;
        while(lo<hi){
            ll mid = lo + (hi-lo)/2;
            tmp.clear();
            if(possible(n, p, mid, tmp)){
                hi=mid;
            }else{
                lo=mid+1;
            }
        }
        if(lo<sol1){
            sol1 = lo;
            sol.clear();
            possible(n, p, lo, sol);
            for(int j=i;j<4;j++){
                for(AABB& k:sol) k.rotate90();
            }
        }
        rotate90(n, p);
        prepare_dp();
    }
    return sol1;
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++) scanf("%lld%lld", &p[i].X, &p[i].Y);
    prepare_dp();
    vector<AABB> sol;
    switch(k){
    case 1: solve1(n, p, sol); break;
    case 2: solve2(n, p, sol); break;
    case 3: solve3(n, p, sol); break;
    default: return -1; break;
    }
    for(int i=0;i<sol.size();i++){
        printf("%lld %lld %lld\n", sol[i].a.X, sol[i].a.Y, sol[i].max_dim());
    }
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<AABB>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~
izvanzemaljci.cpp:280:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  280 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:281:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  281 |     for(int i=0;i<n;i++) scanf("%lld%lld", &p[i].X, &p[i].Y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 12 / 12
• Subtask 4: 30 / 30
• Subtask 5: 32 / 32