Submission #693923

#	Time	Username	Problem	Language	Result	Execution time	Memory
693923		79brue	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	64 ms	11724 KiB

izvanzemaljci

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;

void solve1();
void solve2();

int main(){
    scanf("%d %d", &n, &k);
    if(n==1){
        ll x, y;
        scanf("%lld %lld", &x, &y);
        for(int i=0; i<k; i++) printf("%lld %lld 1\n", x+i+i, y+i+i);
        return 0;
    }
    if(k==1) solve1();
    else if(k==2) solve2();
}

void solve1(){
    ll xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9;
    for(int i=1; i<=n; i++){
        ll x, y;
        scanf("%lld %lld", &x, &y);
        xMin = min(x, xMin), yMin = min(y, yMin);
        xMax = max(x, xMax), yMax = max(y, yMax);
    }
    printf("%lld %lld %lld", xMin, yMin, max(xMax - xMin, yMax - yMin));
}

void solve2(){
    vector<pair<ll, ll> > points (n);
    vector<ll> x(n), y(n);
    vector<ll> xMin1(n, 1e9), xMax1(n, -1e9), yMin1(n, 1e9), yMax1(n, -1e9);
    vector<ll> xMin2(n, 1e9), xMax2(n, -1e9), yMin2(n, 1e9), yMax2(n, -1e9);
    for(int i=0; i<n; i++) scanf("%lld %lld", &points[i].first, &points[i].second);
    sort(points.begin(), points.end());

    /// 가로로 찾기
    for(int i=0; i<n; i++){
        xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first;
        yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second;
    }
    for(int i=1; i<n; i++){
        xMin1[i] = min(xMin1[i], xMin1[i-1]);
        xMax1[i] = max(xMax1[i], xMax1[i-1]);
        yMin1[i] = min(yMin1[i], yMin1[i-1]);
        yMax1[i] = max(yMax1[i], yMax1[i-1]);
    }
    for(int i=n-2; i>=0; i--){
        xMin2[i] = min(xMin2[i], xMin2[i+1]);
        xMax2[i] = max(xMax2[i], xMax2[i+1]);
        yMin2[i] = min(yMin2[i], yMin2[i+1]);
        yMax2[i] = max(yMax2[i], yMax2[i+1]);
    }

    ll justone = max({1LL, xMax1[n-1] - xMin1[n-1], yMax1[n-1] - yMin1[n-1]}); /// 전체 하나로 할 경우의 답
    ll ans = INT_MAX;
    int ansIdx = -1, ansMode = -1;
    for(int i=0; i<n-1; i++){ /// i 기준 정렬
        if(x[i] == x[i+1]) continue;
        ll tmp = max({1LL, xMax1[i] - xMin1[i], yMax1[i] - yMin1[i], xMax2[i+1] - xMin2[i+1], yMax2[i+1] - yMin2[i+1]});
        if(ans > tmp) ans = tmp, ansIdx = i, ansMode = 0;
    }

    /// 세로로 찾기
    sort(points.begin(), points.end(), [&](auto &a, auto &b){
        return a.second < b.second;
    });

    /// 가로로 찾기
    for(int i=0; i<n; i++){
        xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first;
        yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second;
    }
    for(int i=1; i<n; i++){
        xMin1[i] = min(xMin1[i], xMin1[i-1]);
        xMax1[i] = max(xMax1[i], xMax1[i-1]);
        yMin1[i] = min(yMin1[i], yMin1[i-1]);
        yMax1[i] = max(yMax1[i], yMax1[i-1]);
    }
    for(int i=n-2; i>=0; i--){
        xMin2[i] = min(xMin2[i], xMin2[i+1]);
        xMax2[i] = max(xMax2[i], xMax2[i+1]);
        yMin2[i] = min(yMin2[i], yMin2[i+1]);
        yMax2[i] = max(yMax2[i], yMax2[i+1]);
    }

    for(int i=0; i<n-1; i++){ /// i 기준 정렬
        if(y[i] == y[i+1]) continue;
        ll tmp = max({1LL, xMax1[i] - xMin1[i], yMax1[i] - yMin1[i], xMax2[i+1] - xMin2[i+1], yMax2[i+1] - yMin2[i+1]});
        if(ans > tmp) ans = tmp, ansIdx = i, ansMode = 1;
    }

    /// 답 출력하기
    if(justone <= ans || ansMode == -1){
        printf("%lld %lld %lld\n", xMin1[n-1], yMin1[n-1], justone);
        printf("%lld %lld %lld\n", 2'000'000'000LL, 2'000'000'000LL, justone);
    }
    else if(ansMode == 0){
        sort(points.begin(), points.end());

        /// 가로로 찾기
        for(int i=0; i<n; i++){
            xMin1[i] = xMax1[i] = xMin2[i] = xMax2[i] = x[i] = points[i].first;
            yMin1[i] = yMax1[i] = yMin2[i] = yMax2[i] = y[i] = points[i].second;
        }
        for(int i=1; i<n; i++){
            xMin1[i] = min(xMin1[i], xMin1[i-1]);
            xMax1[i] = max(xMax1[i], xMax1[i-1]);
            yMin1[i] = min(yMin1[i], yMin1[i-1]);
            yMax1[i] = max(yMax1[i], yMax1[i-1]);
        }
        for(int i=n-2; i>=0; i--){
            xMin2[i] = min(xMin2[i], xMin2[i+1]);
            xMax2[i] = max(xMax2[i], xMax2[i+1]);
            yMin2[i] = min(yMin2[i], yMin2[i+1]);
            yMax2[i] = max(yMax2[i], yMax2[i+1]);
        }

        printf("%lld %lld %lld\n", xMax1[ansIdx] - ans, yMin1[ansIdx], ans);
        printf("%lld %lld %lld\n", xMin2[ansIdx+1], yMin2[ansIdx+1], ans);
    }
    else{
        printf("%lld %lld %lld\n", xMin1[ansIdx], yMax1[ansIdx] - ans, ans);
        printf("%lld %lld %lld\n", xMin2[ansIdx+1], yMin2[ansIdx+1], ans);
    }
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'void solve1()':
izvanzemaljci.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'void solve2()':
izvanzemaljci.cpp:40:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(int i=0; i<n; i++) scanf("%lld %lld", &points[i].first, &points[i].second);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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