oj.uz

Submission #961952

# Submission time Handle Problem Language Result Execution time Memory
961952 2024-04-12T19:56:47 Z Vladth11 Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 139 ms 57608 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 = 400005;
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);
        }
        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();
    }
}
 
vector <int> nrmX;
vector <int> nrmY;
int codedX[NMAX];
int codedY[NMAX];
unordered_map <int, int> mpX;
unordered_map <int, int> mpY;
 
vector <int> ev1[NMAX];
vector <int> ev2[NMAX];
vector <int> ev3[NMAX];
vector <int> ev4[NMAX];
 
int sum1[NMAX];
int sum2[NMAX];
int sum3[NMAX];
int sum4[NMAX];
 
int f[NMAX];
 
struct ura {
    int unu, doi, trei, patru;
} plec[NMAX];
 
void add(int x, int val) {
    if(plec[x].unu != -1) {
        sum1[plec[x].unu] += val;
    }
    if(plec[x].doi != -1) {
        sum2[plec[x].doi] += val;
    }
    if(plec[x].trei != -1) {
        sum3[plec[x].trei] += val;
    }
    if(plec[x].patru != -1) {
        sum4[plec[x].patru] += val;
    }
}
 
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);
    for(i = 1; i <= n; i++) {
        nrmX.push_back(v[i].x1);
        nrmX.push_back(v[i].x2);
        nrmY.push_back(v[i].y2);
        nrmY.push_back(v[i].y1);
    }
    sort(nrmX.begin(), nrmX.end());
    sort(nrmY.begin(), nrmY.end());
    int cnt = 0;
    int lst = -1;
    for(auto x : nrmX) {
        if(x != lst) {
            cnt++;
        }
        mpX[x] = cnt;
        codedX[cnt] = x;
        lst = x;
    }
    cnt = 0;
    lst = -1;
    for(auto x : nrmY) {
        if(x != lst) {
            cnt++;
        }
        mpY[x] = cnt;
        codedY[cnt] = x;
        lst = x;
    }
    for(i = 1; i <= n; i++) {
        v[i].x1 = mpX[v[i].x1];
        v[i].x2 = mpX[v[i].x2];
        v[i].y1 = mpY[v[i].y1];
        v[i].y2 = mpY[v[i].y2];
    }
    int x1 = INF, x2 = 0, y1 = INF, y2 = 0;
    for(i = 1; i <= n; i++) {
        x1 = min(x1, v[i].x2);
        x2 = max(x2, v[i].x1);
        y1 = min(y1, v[i].y2);
        y2 = max(y2, v[i].y1);
    }
    pii unu = {x1, y1};
    pii doi = {x2, y1};
    pii trei = {x2, y2};
    pii patru = {x1, y2};
    int total = 0;
    for(i = 1; i <= n; i++) {
        plec[i] = {-1, -1, -1, -1};
        if(v[i].y1 <= y1 && v[i].y2 >= y1) {
            int st = max(unu.first, v[i].x1);
            int dr = v[i].x2 + 1;
            assert(st <= dr);
            if(st <= x2) {
                ev1[st].push_back(i);
            }
            if(dr <= x2) {
                ev1[dr].push_back(-i);
                plec[i].unu = v[i].x2;
                sum1[v[i].x2]++;
            }
        }
        if(v[i].x1 <= doi.first && v[i].x2 >= doi.first) {
            int st = max(doi.second, v[i].y1);
            int dr = v[i].y2 + 1;
            assert(st <= dr);
            if(st <= y2) {
                ev2[st].push_back(i);
            }
            if(dr <= y2) {
                ev2[dr].push_back(-i);
                plec[i].doi = v[i].y2;
                sum2[v[i].y2]++;
            }
        }
        if(v[i].y1 <= trei.second && v[i].y2 >= trei.second) {
            int st = min(trei.first, v[i].x2);
            int dr = v[i].x1 - 1;
            assert(st >= dr);
            if(st >= x1) {
                ev3[st].push_back(i);
            }
            if(dr >= x1) {
                ev3[dr].push_back(-i);
                plec[i].trei = v[i].x1;
                sum3[v[i].x1]++;
            }
        }
        if(v[i].x1 <= patru.first && v[i].x2 >= patru.first) {
            int st = min(patru.second, v[i].y2);
            int dr = v[i].y1 - 1;
            assert(st >= dr);
            if(st >= y1) {
                ev4[st].push_back(i);
            }
            if(dr >= y1) {
                ev4[dr].push_back(-i);
                plec[i].patru = v[i].y1;
                sum4[v[i].y1]++;
            }
        }
    }
    for(i = 1; i <= n; i++) {
        int x = i;
        if(isIn(unu, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(doi, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(trei, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(patru, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
    }
    while(unu.first <= x2) {
        if(unu.first != x1) {
            for(auto x : ev1[unu.first]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        while(doi.second < y2 && sum2[doi.second] == 0) {
            doi.second++;
            for(auto x : ev2[doi.second]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        while(trei.first > x1 && sum3[trei.first] == 0) {
            trei.first--;
            for(auto x : ev3[trei.first]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
 
        while(patru.second > y1 && sum4[patru.second] == 0) {
            patru.second--;
            for(auto x : ev4[patru.second]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        if(total == n) {
            cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
            cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
            cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
            cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
            return 0;
        }
        unu.first++;
    }
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 43468 KB Output is correct
2 Correct 15 ms 43612 KB Output is correct
3 Correct 13 ms 43612 KB Output is correct
4 Correct 12 ms 43612 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43636 KB Output is correct
2 Correct 11 ms 43612 KB Output is correct
3 Correct 12 ms 43640 KB Output is correct
4 Correct 12 ms 43620 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43644 KB Output is correct
2 Correct 10 ms 43608 KB Output is correct
3 Correct 13 ms 43488 KB Output is correct
4 Correct 10 ms 43620 KB Output is correct
5 Correct 12 ms 43616 KB Output is correct
6 Correct 11 ms 43616 KB Output is correct
7 Correct 12 ms 43572 KB Output is correct
8 Correct 11 ms 43640 KB Output is correct
9 Correct 13 ms 43612 KB Output is correct
10 Correct 11 ms 43620 KB Output is correct
11 Correct 12 ms 43620 KB Output is correct
12 Correct 11 ms 43620 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 43644 KB Output is correct
2 Correct 13 ms 43620 KB Output is correct
3 Correct 11 ms 43584 KB Output is correct
4 Correct 12 ms 43612 KB Output is correct
5 Correct 12 ms 43608 KB Output is correct
6 Correct 12 ms 43612 KB Output is correct
7 Correct 11 ms 43612 KB Output is correct
8 Correct 11 ms 43612 KB Output is correct
9 Correct 11 ms 43612 KB Output is correct
10 Correct 11 ms 43636 KB Output is correct
11 Correct 13 ms 43636 KB Output is correct
12 Correct 12 ms 43636 KB Output is correct
13 Correct 14 ms 43612 KB Output is correct
14 Incorrect 19 ms 54508 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 18 ms 43468 KB Output is correct
2 Correct 15 ms 43612 KB Output is correct
3 Correct 13 ms 43612 KB Output is correct
4 Correct 12 ms 43612 KB Output is correct
5 Correct 89 ms 57344 KB Output is correct
6 Correct 69 ms 57216 KB Output is correct
7 Correct 73 ms 57220 KB Output is correct
8 Correct 73 ms 57416 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43636 KB Output is correct
2 Correct 11 ms 43612 KB Output is correct
3 Correct 12 ms 43640 KB Output is correct
4 Correct 12 ms 43620 KB Output is correct
5 Correct 92 ms 57232 KB Output is correct
6 Correct 85 ms 57356 KB Output is correct
7 Correct 74 ms 57356 KB Output is correct
8 Correct 82 ms 57424 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43644 KB Output is correct
2 Correct 10 ms 43608 KB Output is correct
3 Correct 13 ms 43488 KB Output is correct
4 Correct 10 ms 43620 KB Output is correct
5 Correct 12 ms 43616 KB Output is correct
6 Correct 11 ms 43616 KB Output is correct
7 Correct 12 ms 43572 KB Output is correct
8 Correct 11 ms 43640 KB Output is correct
9 Correct 13 ms 43612 KB Output is correct
10 Correct 11 ms 43620 KB Output is correct
11 Correct 12 ms 43620 KB Output is correct
12 Correct 11 ms 43620 KB Output is correct
13 Correct 93 ms 57420 KB Output is correct
14 Correct 103 ms 57608 KB Output is correct
15 Correct 88 ms 57420 KB Output is correct
16 Correct 94 ms 57412 KB Output is correct
17 Correct 91 ms 57224 KB Output is correct
18 Correct 98 ms 57428 KB Output is correct
19 Correct 89 ms 57220 KB Output is correct
20 Correct 95 ms 57348 KB Output is correct
21 Correct 139 ms 57352 KB Output is correct
22 Correct 131 ms 57428 KB Output is correct
23 Correct 106 ms 57484 KB Output is correct
24 Correct 121 ms 57356 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 43644 KB Output is correct
2 Correct 13 ms 43620 KB Output is correct
3 Correct 11 ms 43584 KB Output is correct
4 Correct 12 ms 43612 KB Output is correct
5 Correct 12 ms 43608 KB Output is correct
6 Correct 12 ms 43612 KB Output is correct
7 Correct 11 ms 43612 KB Output is correct
8 Correct 11 ms 43612 KB Output is correct
9 Correct 11 ms 43612 KB Output is correct
10 Correct 11 ms 43636 KB Output is correct
11 Correct 13 ms 43636 KB Output is correct
12 Correct 12 ms 43636 KB Output is correct
13 Correct 14 ms 43612 KB Output is correct
14 Incorrect 19 ms 54508 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -