Submission #1237892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237892		goodpjw2008	Hamburg Steak (JOI20_hamburg)	C++20	21 / 100	3093 ms	4948 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{
    int 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 (ll)(a.x2-a.x1+1)*(a.x2-a.x1+1)+(ll)(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);
}
static inline __attribute__((always_inline)) ld cost2(rect &prv, rect cur){
    ll x1=prv.x2-prv.x1,x2=cur.x2-cur.x1,y1=prv.y2-prv.y1,y2=cur.y2-cur.y1;
    return ld(x2-x1)+ld(y2-y1);
}
static inline __attribute__((always_inline)) ld cost3(rect &prv, rect cur){
    ll x1=prv.x2-prv.x1,x2=cur.x2-cur.x1,y1=prv.y2-prv.y1,y2=cur.y2-cur.y1;
    return ld(x2-x1)/x1+ld(y2-y1)/y1;
}
int main(){
    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;
    }
    minstd_rand rng(chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> r(0, 3), rr(0, k-1);
    while(1){
        for(int i = 0; i < k; i++){
            inter[i]=arr[i];
        }
        for(int i = k; i < n; i++){
            ld mx=-5e18;
            ll mi;
            if(r(rng)==0){
                for(int j = 0; j < k; j++){
                    if(cost2(inter[j],intersect(inter[j],arr[i]))>mx){
                        mx=cost2(inter[j],intersect(inter[j],arr[i]));
                        mi=j;
                    }
                }
            }
            else if(r(rng)==1){
                for(int j = 0; j < k; j++){
                    if(cost3(inter[j],intersect(inter[j],arr[i]))>mx){
                        mx=cost3(inter[j],intersect(inter[j],arr[i]));
                        mi=j;
                    }
                }
            }
            else{
                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]);
            if(!area(inter[mi]))break;
        }
        bool f=1;
        for(int i = 0; i < k; i++){
            if(!area(inter[i]))f=0;
        }
        if(f){
            for(int i = 0; i < k; i++){
                cout<<inter[i].x1<<' '<<inter[i].y1<<'\n';
            }
            return 0;
        }
        shuffle(arr,arr+n,rng);
    }
}

• 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: 6 / 6
• Subtask 8: 0 / 79