oj.uz

Submission #693916

# Submission time Handle Problem Language Result Execution time Memory
693916 2023-02-03T11:45:29 Z 79brue Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 65 ms 11852 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], 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", 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 28 ms 292 KB Output is correct
8 Correct 24 ms 292 KB Output is correct
9 Correct 23 ms 212 KB Output is correct
10 Correct 24 ms 292 KB Output is correct
11 Correct 23 ms 212 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 54 ms 11748 KB Output is correct
11 Correct 56 ms 11748 KB Output is correct
12 Correct 65 ms 11756 KB Output is correct
13 Correct 52 ms 11700 KB Output is correct
14 Correct 50 ms 11724 KB Output is correct
15 Correct 59 ms 11624 KB Output is correct
16 Incorrect 61 ms 11852 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Unexpected end of file - int64 expected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -