Submission #617407

#	Time	Username	Problem	Language	Result	Execution time	Memory
617407		alireza_kaviani	Hamburg Steak (JOI20_hamburg)	C++17	3 / 100	154 ms	12948 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , k , L[MAXN] , R[MAXN] , D[MAXN] , U[MAXN] , mark[MAXN];
vector<int> ord;
vector<pii> ans;

int cmp(int x , int y){
    return U[x] < U[y];
}

void solve(int k){
    int x = MOD;
    for(int i : ord){
        if(mark[i]) continue;
        x = min(x , R[i]);
    }
    if(x == MOD){
        for(int i = 0 ; i < ::k ; i++){
            cout << ans[i % SZ(ans)].X << sep << ans[i % SZ(ans)].Y << endl;
        }
        exit(0);
    }
    if(k <= 0)  return;
    int mx = -MOD;
    vector<int> vec;
    for(int i : ord){
        if(mark[i]) continue;
        if(R[i] < x || x < L[i])    continue;
        if(mx < D[i]){
            mx = U[i];
            vec.push_back(D[i]);
            vec.push_back(U[i]);
        }
    }
    if(SZ(vec) > 2 * k) return;
    for(int y : vec){
        for(int i : ord){
            if(mark[i]) continue;
            if(L[i] <= x && x <= R[i] && D[i] <= y && y <= U[i]){
                mark[i] = k;
            }
        }
        ans.push_back({x , y});
        solve(k - 1);
        ans.pop_back();
        for(int i : ord){
            if(mark[i] == k){
                mark[i] = 0;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n >> k;
    for(int i = 0 ; i < n ; i++){
        cin >> L[i] >> D[i] >> R[i] >> U[i];
        ord.push_back(i);
    }
    sort(all(ord) , cmp);

    solve(k);

    return 0;
}
/*

*/

• Subtask 1: 1 / 1
• Subtask 2: 1 / 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