oj.uz

Submission #961707

# Submission time Handle Problem Language Result Execution time Memory
961707 2024-04-12T10:56:19 Z Vladth11 Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 143 ms 16144 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#define int ll

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200001;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

struct rect {
    int x1, y1, x2, y2;
} v[NMAX];

int n, k;
vector <pii> sol;
int taken[NMAX];

rect intersect(rect a, rect b) {
    rect sol = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)};
    return sol;
}

bool isIn(pii a, rect r) {
    return (r.x1 <= a.first && a.first <= r.x2 && r.y1 <= a.second && a.second <= r.y2);
}

rect solve1() {
    int i;
    rect sol = {0, 0, INF, INF};
    for(i = 1; i <= n; i++) {
        sol = intersect(sol, v[i]);
    }
    return sol;
}

void afiseaza() {
    for(auto x : sol) {
        cout << x.first << " " << x.second << "\n";
    }
    k -= sol.size();
    while(k--) {
        cout << "0 0\n";
    }
    exit(0);
}

void tryy(int lvl) {
    int i;
    if(lvl == 0) {
        int ok = 1;
        for(i = 1; i <= n; i++) {
            ok &= (taken[i] > 0); /// hai ca e bine daca e
        }
        if(ok) {
            afiseaza();
        }
        return;
    }
    int xmin = INF, xmax = 0, ymin = INF, ymax = 0;
    for(i = 1; i <= n; i++) {
        if(taken[i]) continue;
        xmin = min(xmin, v[i].x2);
        xmax = max(xmax, v[i].x1);
        ymin = min(ymin, v[i].y2);
        ymax = max(ymax, v[i].y1);
    }
    vector <pii> per;
    per.push_back({xmin, ymin});
    per.push_back({xmin, ymax});
    per.push_back({xmax, ymin});
    per.push_back({xmax, ymax});
    for(int d = 0; d < 4; d++) {
        pii acum = per[d];
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) {
                taken[i]++;
            }
        }
        sol.push_back(acum);
        tryy(lvl - 1);
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) taken[i]--;
        }
        sol.pop_back();
    }
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; /// it doesn't matter
    }
    /// K = 1?
    tryy(1);
    /// K = 2?
    tryy(2);
    /// K = 3?
    tryy(3);
    /// K = 4 and pair found
    tryy(4);
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2528 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2596 KB Output is correct
2 Correct 2 ms 2604 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2528 KB Output is correct
6 Correct 1 ms 2404 KB Output is correct
7 Correct 1 ms 2532 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2400 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2400 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2532 KB Output is correct
2 Correct 2 ms 2572 KB Output is correct
3 Correct 2 ms 2404 KB Output is correct
4 Correct 2 ms 2408 KB Output is correct
5 Correct 2 ms 2604 KB Output is correct
6 Correct 2 ms 2608 KB Output is correct
7 Correct 3 ms 2620 KB Output is correct
8 Correct 3 ms 2540 KB Output is correct
9 Correct 3 ms 2536 KB Output is correct
10 Correct 3 ms 2408 KB Output is correct
11 Correct 2 ms 2408 KB Output is correct
12 Correct 2 ms 2604 KB Output is correct
13 Correct 5 ms 2660 KB Output is correct
14 Incorrect 5 ms 2396 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 63 ms 12208 KB Output is correct
6 Correct 68 ms 12108 KB Output is correct
7 Correct 66 ms 12220 KB Output is correct
8 Correct 69 ms 12112 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2528 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 65 ms 15956 KB Output is correct
6 Correct 67 ms 15952 KB Output is correct
7 Correct 69 ms 15800 KB Output is correct
8 Correct 69 ms 15812 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2596 KB Output is correct
2 Correct 2 ms 2604 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2528 KB Output is correct
6 Correct 1 ms 2404 KB Output is correct
7 Correct 1 ms 2532 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2400 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2400 KB Output is correct
13 Correct 85 ms 16000 KB Output is correct
14 Correct 86 ms 16144 KB Output is correct
15 Correct 86 ms 15956 KB Output is correct
16 Correct 88 ms 15952 KB Output is correct
17 Correct 81 ms 15944 KB Output is correct
18 Correct 83 ms 15892 KB Output is correct
19 Correct 80 ms 15936 KB Output is correct
20 Correct 85 ms 15936 KB Output is correct
21 Correct 139 ms 15932 KB Output is correct
22 Correct 123 ms 15828 KB Output is correct
23 Correct 111 ms 16008 KB Output is correct
24 Correct 143 ms 15800 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2532 KB Output is correct
2 Correct 2 ms 2572 KB Output is correct
3 Correct 2 ms 2404 KB Output is correct
4 Correct 2 ms 2408 KB Output is correct
5 Correct 2 ms 2604 KB Output is correct
6 Correct 2 ms 2608 KB Output is correct
7 Correct 3 ms 2620 KB Output is correct
8 Correct 3 ms 2540 KB Output is correct
9 Correct 3 ms 2536 KB Output is correct
10 Correct 3 ms 2408 KB Output is correct
11 Correct 2 ms 2408 KB Output is correct
12 Correct 2 ms 2604 KB Output is correct
13 Correct 5 ms 2660 KB Output is correct
14 Incorrect 5 ms 2396 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -