oj.uz

Submission #759905

# Submission time Handle Problem Language Result Execution time Memory
759905 2023-06-17T03:54:57 Z 1075508020060209tc Hamburg Steak (JOI20_hamburg) C++14
3 / 100
 3000 ms 96896 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=1e9;
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+2;kk++){
        mnr=1e9;
    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;
            mp[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);
return 0;
for(int i=0;i<K;i++){
    cout<<"1 1\n";
}



}

/*
1 1 1 5
1 3 1 7
1 6 1 9
1 8 1 10
*/

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:61: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]
   61 |     for(int i=0;i<vr.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 996 KB Output is correct
4 Correct 3 ms 980 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 57 ms 1552 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 4 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 477 ms 56600 KB Output is correct
6 Correct 459 ms 56668 KB Output is correct
7 Correct 440 ms 56600 KB Output is correct
8 Correct 483 ms 56596 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 884 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 513 ms 62428 KB Output is correct
6 Execution timed out 3064 ms 96896 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 996 KB Output is correct
4 Correct 3 ms 980 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 57 ms 1552 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -