Submission #1237878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237878		goodpjw2008	Hamburg Steak (JOI20_hamburg)	C++20	15 / 100	3095 ms	6704 KiB

hamburg

#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,ssse3")
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
struct rect{
    ll x1,y1,x2,y2;
}arr[200002],inter[5];
static inline __attribute__((always_inline)) rect intersect(rect a, rect b){
    return {max(a.x1,b.x1),max(a.y1,b.y1),min(a.x2,b.x2),min(a.y2,b.y2)};
}
static inline __attribute__((always_inline)) ll area(rect a){
    if(a.x2<a.x1||a.y2<a.y1)return 0;
    return (a.x2-a.x1+1)*(a.x2-a.x1+1)+(a.y2-a.y1+1)*(a.y2-a.y1+1);
}
static inline __attribute__((always_inline)) ld cost(rect prv, rect cur){
    return (ld)(area(cur)-area(prv))/area(prv);
}
vector<pll>ans;
int main(){
    srand(time(NULL));
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;
    cin>>n>>k;
    k=min(k,n);
    for(int i = 0; i < n; i++){
        cin>>arr[i].x1>>arr[i].y1>>arr[i].x2>>arr[i].y2;
    }
    while(1){
        random_shuffle(arr,arr+n);
        for(int i = 0; i < k; i++){
            inter[i]=arr[i];
        }
        for(int i = k; i < n; i++){
            ld mx=-5e18;
            ll mi;
            for(int j = 0; j < k; j++){
                if(cost(inter[j],intersect(inter[j],arr[i]))>mx){
                    mx=cost(inter[j],intersect(inter[j],arr[i]));
                    mi=j;
                }
            }
            inter[mi]=intersect(inter[mi],arr[i]);
        }
        ans.clear();
        bool f=1;
        for(int i = 0; i < k; i++){
            if(area(inter[i])){
                ans.push_back({inter[i].x1,inter[i].y1});
            }
            else f=0;
        }
        if(f){
            for(pll t:ans){
                cout<<t.x<<' '<<t.y<<'\n';
            }
            if(ans.size()<k){
                for(int i = ans.size(); i < k; i++){
                    cout<<ans[0].x<<' '<<ans[0].y<<'\n';
                }
            }
            return 0;
        }
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79