제출 #1359832

#제출 시각아이디문제언어결과실행 시간메모리
1359832eradaxCutting a Rectangle (BOI24_rectangle)C++20
0 / 100
64 ms156960 KiB
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    ll ar=0;
    int k;cin>>k;
    vector<pair<int,int>> a(k);
    vector<int> b(5'000'001,-1);
    vector<int> vis(5'000'001);
    vector<vector<int>> c(5'000'001);
    vector<int> sd;
    for(int x=0;x<k;x++){
        auto&[i,j]=a[x];
        cin>>i>>j,sd.insert(end(sd),{i,j}),ar+=(ll)i*j,b[i]=x,c[j].push_back(x);
    }

    sort(begin(sd),end(sd));sd.erase(unique(begin(sd),end(sd)),end(sd));
    
    vector<int> ans;
    for(int i:sd){
        vis.assign(ssize(vis),0);

        ll ls=ar/i;
        ll ss=i;
        if(ls<ss)tie(ls,ss)={ss,ls};

        int kk=0;
        for(int kp=0;kp<k;kp++){
            if(ls<ssize(b)&&b[ls]!=-1&&vis[b[ls]]==0){
                vis[b[ls]]=1;
                ss-=a[b[ls]].second;
                if(ss<0)break;
                kk++;
                continue;
            }

            if(b[ss]!=-1&&vis[b[ss]]==0){
                vis[b[ss]]=1;
                ls-=a[b[ss]].second;
                if(ls<0)break;
                if(ls<ss)swap(ls,ss);
                kk++;
                continue;
            }

            for(int i:c[ss])if(!vis[i]){
                vis[i]=1;
                ls-=a[i].first;
                if(ls<0)break;
                kk++;
            }
            if(ls<ss)swap(ls,ss);
        }

        if(kk==k)ans.push_back(i);
    }

    cout<<ssize(ans)<<'\n';
    for(int i:ans)cout<<i<<' ';
    cout<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...