oj.uz

Submission #617407

# Submission time Handle Problem Language Result Execution time Memory
617407 2022-08-01T11:13:12 Z alireza_kaviani Hamburg Steak (JOI20_hamburg) C++17
3 / 100
 154 ms 12948 KB 
#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.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 472 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 476 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Incorrect 3 ms 468 KB Unexpected end of file - int32 expected
11 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Incorrect 4 ms 472 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 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 127 ms 12836 KB Output is correct
6 Correct 125 ms 12948 KB Output is correct
7 Correct 122 ms 12924 KB Output is correct
8 Correct 142 ms 12820 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 125 ms 12876 KB Output is correct
6 Incorrect 154 ms 12816 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 472 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 476 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Incorrect 3 ms 468 KB Unexpected end of file - int32 expected
11 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

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