oj.uz

답안 #693914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
693914 2023-02-03T11:41:02 Z 79brue Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 25 ms 304 KB 
#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(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], yMax1[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], yMax2[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", INT_MAX, INT_MAX, justone);
    }
    else if(ansMode == 0){
        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

izvanzemaljci.cpp: In function 'void solve2()':
izvanzemaljci.cpp:102:20: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  102 |         printf("%lld %lld %lld\n", INT_MAX, INT_MAX, justone);
      |                 ~~~^
      |                    |
      |                    long long int
      |                 %d
izvanzemaljci.cpp:102:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
  102 |         printf("%lld %lld %lld\n", INT_MAX, INT_MAX, justone);
      |                      ~~~^
      |                         |
      |                         long long int
      |                      %d
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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 23 ms 288 KB Output is correct
8 Correct 23 ms 212 KB Output is correct
9 Correct 23 ms 212 KB Output is correct
10 Correct 25 ms 212 KB Output is correct
11 Correct 24 ms 212 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int64 expected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -