Submission #1002972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002972		hyakup	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	57 ms	3156 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int> 


const int inf = 1e9 + 10; 

void solve1( vector<pii>& v ){
    int x1 = inf, x2 = -inf, y1 = inf, y2 = -inf; 
    for( auto [x, y] : v ){
        x1 = min( x1, x ); 
        x2 = max( x2, x ); 
        y1 = min( y1, y ); 
        y2 = max( y2, y ); 
    }

    int tam = max( x2 - x1, y2 - y1 ); 
    tam = max( tam, 1 );
    cout << x1 << " " << y1 << " " << tam << endl;
}

struct rect{
    int x, y, tam; rect( int x = 0, int y = 0, int tam = inf ) :x(x), y(y), tam(tam)  {}
}; 

void solve2( vector<pii>& v ){
    if( v.size() == 1 ){
        cout << v[0].first << " " << v[0].second << " " << 1 << endl;
        cout << 2*inf << " " << 2*inf << " " << 1 << endl;
        return; 
    }

    sort( v.begin(), v.end(), [&]( pii a, pii b ){
        if( a.first == b.first ) return a.second < b.second; 
        return a.first < b.first; 
    }); // ordena por x;    
    vector<rect> resp( v.size() ); 

    if( v.size() == 2 ){
        cout << v[0].first - 1 << " " << v[0].first - 1 << " " << 1 << endl;
        cout << v[1].first << " " << v[1].first << " " << 1 << endl;
        return; 
    }

    int x1 = inf, x2 = -inf, y1 = inf, y2 = -inf; 
    for( int i = 0; i < v.size(); i++ ){
        auto [x, y] = v[i]; 
        x1 = min( x1, x ); 
        x2 = max( x2, x ); 
        y1 = min( y1, y ); 
        y2 = max( y2, y ); 
        if( v[i + 1].first != v[i].first ) resp[i] = rect( x2 - max( x2 - x1, y2 - y1 ), y2 - max( x2 - x1, y2 - y1 ), max( x2 - x1, y2 - y1 ) );
        else if( i > 0 ) resp[i] = resp[i - 1]; 
        resp[i].tam = max( resp[i].tam, 1 ); 
    }

    x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;   

    rect a( 0,0, inf ), b( 0, 0, inf ); 

    for( int i = v.size() - 1; i > 0; i-- ){
        auto [x, y] = v[i]; 
        x1 = min( x1, x ); 
        x2 = max( x2, x ); 
        y1 = min( y1, y ); 
        y2 = max( y2, y ); 
        rect cur( x1, y1, max( x2 - x1, y2 - y1 ) );

        if( v[i - 1].first != v[i].first && max( cur.tam, resp[i - 1].tam ) < max( a.tam, b.tam ) ){
            a = cur; 
            b = resp[i - 1]; 
            a.tam = max( a.tam, 1 ); 
            b.tam = max( b.tam, 1 ); 
        }
    }
    /////////////////////////////////////////////////////////////////////////////////////////
    sort( v.begin(), v.end(), [&]( pii a, pii b ){
        return a.second < b.second; 
    }); // ordena por y;    
    resp.clear(); 
    resp.resize(v.size()); 

    x1 = inf, x2 = -inf, y1 = inf, y2 = -inf; 
    for( int i = 0; i < v.size(); i++ ){
        auto [x, y] = v[i]; 
        x1 = min( x1, x ); 
        x2 = max( x2, x ); 
        y1 = min( y1, y ); 
        y2 = max( y2, y ); 
        if( v[i].second != v[i + 1].second ) resp[i] = rect( x2 - max( x2 - x1, y2 - y1 ), y2 - max( x2 - x1, y2 - y1 ), max( x2 - x1, y2 - y1 ) );
        else if( i > 0 ) resp[i] = resp[i - 1]; 
        resp[i].tam = max( resp[i].tam, 1 ); 
    }

    x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;   

    for( int i = v.size() - 1; i > 0; i-- ){

        auto [x, y] = v[i]; 
        x1 = min( x1, x ); 
        x2 = max( x2, x ); 
        y1 = min( y1, y ); 
        y2 = max( y2, y ); 
        rect cur( x1, y1, max( x2 - x1, y2 - y1 ) );

        if( v[i].second != v[i - 1].second && max( cur.tam, resp[i - 1].tam ) < max( a.tam, b.tam ) ){
            a = cur; 
            b = resp[i - 1]; 
            a.tam = max( a.tam, 1 ); 
            b.tam = max( b.tam, 1 ); 
        }
    }
    cout << a.x << " " << a.y << " " << a.tam << endl;
    cout << b.x << " " << b.y << " " << b.tam << endl;
}

int main(){
    int n, k; cin >> n >> k; 
    vector<pii> v(n); 
    for( int i = 0; i < n; i++ ) cin >> v[i].first >> v[i].second; 
    if( k == 1 ) solve1(v); 
    else if( k == 2 ) solve2( v ); 
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'void solve2(std::vector<std::pair<int, int> >&)':
izvanzemaljci.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for( int i = 0; i < v.size(); i++ ){
      |                     ~~^~~~~~~~~~
izvanzemaljci.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for( int i = 0; i < v.size(); i++ ){
      |                     ~~^~~~~~~~~~

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