Submission #759895

#	Time	Username	Problem	Language	Result	Execution time	Memory
759895		1075508020060209tc	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	365 ms	40996 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int K;
pair<pair<int,int>,pair<int,int>>ar[200005];
vector<pair<int,int>>ans;

bool cmp(pair<pair<int,int>,pair<int,int>>i,pair<pair<int,int>,pair<int,int>>j){
if(i.X.X<j.X.X){return 1;}
return 0;
}

void dfs(vector<pair<pair<int,int>,pair<int,int>>>vr,int k){
if(k==0){
    if(vr.size()==0){
        for(int i=0;i<ans.size();i++){
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
        }
        exit(0);
    }
    return;
}

if(vr.size()==0){
    while(ans.size()<K){
        ans.push_back(ans.back());
    }
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
    exit(0);
}

int mnr=1e12;
for(int i=0;i<vr.size();i++){
    mnr=min(mnr,vr[i].second.Y);
}
vector<pair<pair<int,int>,pair<int,int>>>nvr;
for(int i=0;i<vr.size();i++){
    if(vr[i].second.X<=mnr){
        nvr.push_back(vr[i]);
    }
}int omnr=mnr;
map<pair<pair<int,int>,pair<int,int>>,int>mp;
for(int kk=1;kk<=k;kk++){
        mnr=1e12;
    for(int i=0;i<nvr.size();i++){
        if(mp.find(nvr[i])!=mp.end()){continue;}
        mnr=min(mnr,nvr[i].first.second);
    }
    map<pair<pair<int,int>,pair<int,int>>,int>mp2;
    for(int i=0;i<nvr.size();i++){
        if(nvr[i].first.X<=mnr&&nvr[i].first.Y>=mnr){
            mp2[nvr[i]]=1;
        }
    }
    vector<pair<pair<int,int>,pair<int,int>>>nxt;
    for(int i=0;i<vr.size();i++){
        if(mp2.find(vr[i])==mp2.end()){
            nxt.push_back(vr[i]);
        }
    }
    ans.push_back({mnr,omnr});
    dfs(nxt,k-1);
    ans.pop_back();
}





}




signed main(){
cin>>n>>K;
for(int i=1;i<=n;i++){
    cin>>ar[i].first.X>>ar[i].second.X>>ar[i].first.Y>>ar[i].second.Y;
}

vector<pair<pair<int,int>,pair<int,int>>>vr;
for(int i=1;i<=n;i++){
    vr.push_back(ar[i]);
}

dfs(vr,K);




}

Compilation message (stderr)

hamburg.cpp: In function 'void dfs(std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >, long long int)':
hamburg.cpp:18:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0;i<ans.size();i++){
      |                     ~^~~~~~~~~~~
hamburg.cpp:27:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |     while(ans.size()<K){
      |           ~~~~~~~~~~^~
hamburg.cpp:30:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~
hamburg.cpp:37:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 | for(int i=0;i<vr.size();i++){
      |             ~^~~~~~~~~~
hamburg.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 | for(int i=0;i<vr.size();i++){
      |             ~^~~~~~~~~~
hamburg.cpp:49:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<nvr.size();i++){
      |                 ~^~~~~~~~~~~
hamburg.cpp:54:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<nvr.size();i++){
      |                 ~^~~~~~~~~~~
hamburg.cpp:60:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<vr.size();i++){
      |                 ~^~~~~~~~~~

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