제출 #681705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681705		qwerasdfzxcl	Izvanzemaljci (COI21_izvanzemaljci)	C++17	100 / 100	1314 ms	8260 KiB

izvanzemaljci

#include <bits/stdc++.h>
#define int long long

typedef long long ll;
using namespace std;
struct Square{
    ll l, x, y;
    Square(){}
    Square(ll _l, ll _x, ll _y): l(_l), x(_x), y(_y) {}

    void print(){printf("%lld %lld %lld\n", x, y, l);}
};
pair<int, int> a[100100], a0[100100];
ll mn[100100], mx[100100];

void solve1(int n){
    sort(a+1, a+n+1);
    int y1 = a[1].second, y2 = a[1].second;
    for (int i=1;i<=n;i++){
        y1 = min(y1, a[i].second);
        y2 = max(y2, a[i].second);
    }

    Square ans(max(max(a[n].first-a[1].first, y2-y1), 1LL), a[1].first, y1);
    ans.print();
}

pair<int, pair<Square, Square>> solve2x(int n){
    sort(a+1, a+n+1);
    a[n+1].first = 1e9+100;
    mn[n] = a[n].second;
    mx[n] = a[n].second;
    for (int i=n-1;i>0;i--){
        mn[i] = min(mn[i+1], a[i].second);
        mx[i] = max(mx[i+1], a[i].second);
    }

    int y1 = 1e9, y2 = -1e9, ans = 2e9 + 100;
    pair<Square, Square> ret;
    for (int i=1;i<=n;i++){
        y1 = min(y1, a[i].second);
        y2 = max(y2, a[i].second);

        int L1 = max(y2-y1, a[i].first-a[1].first);
        int L2 = max(mx[i+1]-mn[i+1], a[n].first-a[i+1].first);
        L1 = max(L1, 1LL);
        L2 = max(L2, 1LL);

        if (ans > max(L1, L2) && a[i].first < a[i+1].first){
            ans = max(L1, L2);
            ret = make_pair(Square(L1, (ll)a[i].first-L1, (ll)y1), Square(L2, (ll)a[i+1].first, (ll)mn[i+1]));
        }
    }

    return {ans, ret};
}

void solve2(int n){
    auto [ans1, p1] = solve2x(n);
    for (int i=1;i<=n;i++) swap(a[i].first, a[i].second);
    auto [ans2, p2] = solve2x(n);

    auto p = p1;
    if (ans2 < ans1){
        p = p2;
        swap(p.first.x, p.first.y);
        swap(p.second.x, p.second.y);
    }

    p.first.print();
    p.second.print();
}

vector<Square> rans3;
pair<ll, ll> b[100100];
bool solve3x(int s, int e, ll L, ll mnx){
    if (s>e){
        rans3.emplace_back(1, 3e9-5000, 3e9-5000);
        rans3.emplace_back(1, 3e9-6000, 3e9-6000);
        return 1;
    }

    sort(b+s, b+e+1);
    b[e+1].first = 2e9;
    mn[e] = b[e].second;
    mx[e] = b[e].second;
    for (int i=e-1;i>=s;i--){
        mn[i] = min(mn[i+1], b[i].second);
        mx[i] = max(mx[i+1], b[i].second);
    }

    ll y1 = 1e18, y2 = -1e18, ans = 1e18;
    pair<Square, Square> ret;
    for (int i=s;i<=e;i++){
        y1 = min(y1, (ll)b[i].second);
        y2 = max(y2, (ll)b[i].second);

        ll L1 = max(y2-y1, (ll)b[i].first-b[s].first);
        ll L2 = max((ll)mx[i+1]-mn[i+1], (ll)b[e].first-b[i+1].first);
        L1 = max(L1, 1LL);
        L2 = max(L2, 1LL);

        if (ans > max(L1, L2) && b[i].first < b[i+1].first){
            ll X = min(b[i+1].first-1-L1, (ll)b[s].first);
            if (X < mnx) continue;

            ans = max(L1, L2);
            ret = make_pair(Square(L1, X, y1), Square(L2, b[i+1].first, mn[i+1]));
        }
    }

    if (ans <= L){
        rans3.push_back(ret.first);
        rans3.push_back(ret.second);
        return 1;
    }

    return 0;
}

bool solve3xx(int n, ll L){
    rans3.clear();
    sort(a+1, a+n+1);

    ll y1 = 1e18, y2 = -1e18;
    for (int i=1;i<=n+1;){
        int r = i;
        ll py1 = y1, py2 = y2;

        while(r<=n && a[i].first==a[r].first){
            y1 = min(y1, (ll)a[r].second);
            y2 = max(y2, (ll)a[r].second);
            ++r;
        }

        ll len = max((ll)a[i].first - a[1].first, y2-y1);

        if (len > L || i==n+1){
            if (py1==1e18) return 0;

            for (int j=i;j<=n;j++) b[j] = a[j];

            if (solve3x(i, n, L, a[i-1].first+1)){
                ll rlen = max((ll)a[i-1].first - a[1].first, py2-py1);
                rlen = max(rlen, 1LL);
                rans3.emplace_back(rlen, a[i-1].first-rlen, py1);
                return 1;
            }
            return 0;
        }


        i = r;
    }

    assert(0);
}

bool solve3xy(int n, ll L){
    rans3.clear();
    sort(a+1, a+n+1);

    ll y1 = 1e18, y2 = -1e18;
    for (int i=1;i<=n+1;){
        int r = i;
        ll py1 = y1, py2 = y2;

        while(r<=n && a[i].first==a[r].first){
            y1 = min(y1, (ll)a[r].second);
            y2 = max(y2, (ll)a[r].second);
            ++r;
        }

        ll len = max((ll)a[i].first - a[1].first, y2-y1);

        if (len > L || i==n+1){
            if (py1==1e18) return 0;

            for (int j=i;j<=n;j++) b[j] = {a[j].second, a[j].first};

            if (solve3x(i, n, L, -1e18)){
                for (auto &S:rans3) swap(S.x, S.y);
                ll rlen = max((ll)a[i-1].first - a[1].first, py2-py1);
                rlen = max(rlen, 1LL);
                rans3.emplace_back(rlen, a[i-1].first-rlen, py1);
                return 1;
            }
            return 0;
        }


        i = r;
    }

    assert(0);
}

bool ok(int n, ll L){
    for (int i=1;i<=n;i++) a[i] = a0[i];

    //if (L==2) printf("\nok\n");
    if (solve3xx(n, L)) return 1;

    //if (L==2) printf("ok\n");
    if (solve3xy(n, L)) return 1;
    for (int i=1;i<=n;i++) a[i].first = -a[i].first;
    //if (L==2) printf("ok\n");
    if (solve3xx(n, L)){
        for (auto &S:rans3) S.x = -S.x-S.l;
        return 1;
    }
    if (solve3xy(n, L)){
        for (auto &S:rans3) S.x = -S.x-S.l;
        return 1;
    }
    for (int i=1;i<=n;i++) a[i].first = -a[i].first;


    ///swap xy
    for (int i=1;i<=n;i++) swap(a[i].first, a[i].second);

    //if (L==2) printf("ok\n");
    if (solve3xx(n, L)){
        for (auto &S:rans3) swap(S.x, S.y);
        return 1;
    }
    //if (L==2) printf("ok\n");
    if (solve3xy(n, L)){
        for (auto &S:rans3) swap(S.x, S.y);
        return 1;
    }
    for (int i=1;i<=n;i++) a[i].first = -a[i].first;
    //if (L==2) printf("ok\n");
    if (solve3xy(n, L)){
        for (auto &S:rans3) S.x = -S.x-S.l;
        for (auto &S:rans3) swap(S.x, S.y);
        return 1;
    }
    if (solve3xx(n, L)){
        for (auto &S:rans3) S.x = -S.x-S.l;
        for (auto &S:rans3) swap(S.x, S.y);
        return 1;
    }

    return 0;
}

void solve3(int n){
    ll l = 1, r = 2e9+100, ans = -1;
    while(l<=r){
        ll m = (l+r)/2;
        if (ok(n, m)) r = m-1, ans = m;
        else l = m+1;
    }

    assert(ans!=-1);
    assert(ok(n, ans));
    for (auto &S:rans3) S.print();
}

signed main(){
    int n, k;
    scanf("%lld %lld", &n, &k);
    for (int i=1;i<=n;i++) scanf("%lld %lld", &a[i].first, &a[i].second);
    //for (int i=1;i<=n;i++) a[i].first = i, a[i].second = -i;
    for (int i=1;i<=n;i++) a0[i] = a[i];


    if (k==1) solve1(n);
    if (k==2) solve2(n);
    if (k==3) solve3(n);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:263:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:264:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |     for (int i=1;i<=n;i++) scanf("%lld %lld", &a[i].first, &a[i].second);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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