제출 #652817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652817		XCAC197	함박 스테이크 (JOI20_hamburg)	C++14	21 / 100	3072 ms	24604 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200100
#define K 4
#define M 10

struct rec{
    int x1,x2,y1,y2;
    friend rec operator^(const rec&x,const rec&y){
        return {max(x.x1,y.x1),min(x.x2,y.x2),max(x.y1,y.y1),min(x.y2,y.y2)};
    }
    int area(){
        if(x1>x2||y1>y2){return 0;}
        return (x2-x1+1)*(y2-y1+1);
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k;
rec arr[N],res[K];
rec arr2[N];
vector<int>srt;
int weight[N];
bool vis[N];

signed main(){
    cin>>n>>k;
    for(int a=0;a<n;++a){
        cin>>arr[a].x1>>arr[a].y1>>arr[a].x2>>arr[a].y2;
    }
    for(int a=0;a<n;++a) {
        weight[a]=1;
        for (int b = 0; b < M; ++b) {
            int r2=rng()%n;
            if((arr[a]^arr[r2]).area()==0){
                ++weight[a];
            }
        }
    }
    for(int a=0;a<n;++a){
        for(int b=0;b<weight[a];++b) {
            srt.push_back(a);
        }
    }
    while(true){
        shuffle(srt.begin(),srt.end(),rng);
        memset(vis,0,sizeof(vis));
        for(int a=0,b=0;a<srt.size()&&b<n;++a){
            if(vis[srt[a]]){
                continue;
            }
            arr2[b]=arr[srt[a]];
            vis[srt[a]]=true;
            ++b;
        }
        for(int b=0;b<k;++b){
            res[b]=arr2[b];
        }
        bool flag=false;
        //shrink res
        for(int a=k;a<n;++a){
            pair<double,int>p={0,-1};
            for(int b=0;b<k;++b){
                p=max(p,{(1.0*(res[b]^arr2[a]).area())/res[b].area(),b});
            }
            res[p.second]=res[p.second]^arr2[a];
            if(res[p.second].x1>res[p.second].x2||res[p.second].y1>res[p.second].y2){
                flag=true;
                break;
            }
        }
        if(!flag){
            for(int b=0;b<k;++b){
                cout<<res[b].x1<<" "<<res[b].y1<<endl;
            }
            break;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

hamburg.cpp: In function 'int main()':
hamburg.cpp:50:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int a=0,b=0;a<srt.size()&&b<n;++a){
      |                         ~^~~~~~~~~~~

• 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