oj.uz

Submission #759895

# Submission time Handle Problem Language Result Execution time Memory
759895 2023-06-17T03:22:52 Z 1075508020060209tc Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 365 ms 40996 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Incorrect 4 ms 852 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 688 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 4 ms 776 KB Output is correct
8 Incorrect 6 ms 852 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Incorrect 7 ms 852 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 357 ms 40996 KB Output is correct
6 Correct 365 ms 40900 KB Output is correct
7 Correct 350 ms 40916 KB Output is correct
8 Correct 353 ms 40952 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Incorrect 4 ms 852 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 688 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 4 ms 776 KB Output is correct
8 Incorrect 6 ms 852 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Incorrect 7 ms 852 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -