Submission #1237971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237971		goodpjw2008	Hamburg Steak (JOI20_hamburg)	C++20	6 / 100	3096 ms	3400 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;
}
static inline __attribute__((always_inline)) ld cost4(rect &prv, rect cur){
    return (ld)(area(cur)-area(prv));
}
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){
        shuffle(arr,arr+n,rng);
        for(int i = 0; i < k; i++){
            inter[i]=arr[i];
        }
        ll mxx=k-1;
        ll failc=0;
        while(1){
            shuffle(arr+mxx+1,arr+n,rng);
            int f=1;
            for(int i = mxx+1; i < n; i++){
                ld mx=-5e18;
                ll mi;
                ll rd=r(rng);
                if(rd==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(rd==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 if(rd==2){
                    for(int j = 0; j < k; j++){
                        if(cost4(inter[j],intersect(inter[j],arr[i]))>mx){
                            mx=cost4(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;
                        }
                    }
                }
                if(!area(intersect(inter[mi],arr[i]))){
                    if(mxx<i-1){
                        mxx=i-1;
                        failc=0;
                    }
                    else{
                        failc++;
                    }
                    f=0;
                    break;
                }
                inter[mi]=intersect(inter[mi],arr[i]);
            }
            if(f==1){
                for(int i = 0; i < k; i++){
                    cout<<inter[i].x1<<' '<<inter[i].y1<<'\n';
                }
                return 0;
            }
            else if(failc>=10000){
                break;
            }
        }
    }
}

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