oj.uz

Submission #681691

# Submission time Handle Problem Language Result Execution time Memory
681691 2023-01-13T17:47:46 Z qwerasdfzxcl Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 32 ms 1108 KB 
#include <bits/stdc++.h>

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

    void print(){printf("%d %d %d\n", x, y, l);}
};
pair<int, int> a[100100];
int 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), 1), 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 = 1e9;
    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, 1);
        L2 = max(L2, 1);

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

void solve3(int n){

}

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i=1;i<=n;i++) scanf("%d %d", &a[i].first, &a[i].second);
    if (k==1) solve1(n);
    if (k==2) solve2(n);
    if (k==3) solve3(n);
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 32 ms 972 KB Output is correct
8 Correct 30 ms 972 KB Output is correct
9 Correct 30 ms 1064 KB Output is correct
10 Correct 30 ms 1068 KB Output is correct
11 Correct 30 ms 1108 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.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 -

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 -