oj.uz

Submission #414530

# Submission time Handle Problem Language Result Execution time Memory
414530 2021-05-30T15:16:25 Z usachevd0 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 395 ms 29432 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int INF32 = 1e9;

using Point = array<int, 2>;

struct Rect {
    int c[2][2];
    
    Rect() {}
    
    void read() {
        cin >> c[0][0] >> c[1][0] >> c[0][1] >> c[1][1];
    }
    
    bool in(Point P) {
        return c[0][0] <= P[0] && P[0] <= c[0][1] && 
               c[1][0] <= P[1] && P[1] <= c[1][1];
    }
} universe_rect;

Rect intersect(const Rect& r1, const Rect& r2) {
    Rect r3;
    for (int a = 0; a < 2; ++a) {
        r3.c[a][0] = max(r1.c[a][0], r2.c[a][0]);
        r3.c[a][1] = min(r1.c[a][1], r2.c[a][1]);
    }
    return r3;
}

vector<Point> solve(int k, vector<Rect> rects, vector<Point> points) {
    if (rects.empty()) {
        while (k--)
            points.push_back({0, 0});
        return points;
    }
    Rect I = universe_rect;
    for (Rect& r : rects)
        I = intersect(I, r);
    if (k == 1) {
        if (I.c[0][0] > I.c[0][1] || I.c[1][0] > I.c[1][1]) {
            return {};
        } else {
            points.push_back({I.c[0][0], I.c[1][0]});
            return points;
        }
    }
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            Point P{I.c[0][i], I.c[1][j]};
            points.push_back(P);
            vector<Rect> new_rects;
            for (auto r : rects)
                if (!r.in(P))
                    new_rects.push_back(r);
            auto res = solve(k - 1, new_rects, points);
            if (!res.empty()) {
                return res;
            }
            points.pop_back();
        }
    }
    return {};
}

int32_t main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    universe_rect.c[0][0] = universe_rect.c[1][0] = 0;
    universe_rect.c[0][1] = universe_rect.c[1][1] = +INF32;
    
    int n, k;
    cin >> n >> k;
    vector<int> X[2];
    vector<Rect> rects(n);
    for (auto& r : rects) {
        r.read();
        for (int a = 0; a < 2; ++a)
            for (int b = 0; b < 2; ++b)
                X[a].push_back(r.c[a][b]);
    }
    for (int a = 0; a < 2; ++a) {
        sort(all(X[a]));
        X[a].resize(unique(all(X[a])) - X[a].begin());
    }
    for (auto& r : rects)
        for (int a = 0; a < 2; ++a)
            for (int b = 0; b < 2; ++b)
                r.c[a][b] = lower_bound(all(X[a]), r.c[a][b]) - X[a].begin();
    auto easy = solve(k, rects, {});
    if (!easy.empty()) {
        for (auto P : easy)
            cout << X[0][P[0]] << ' ' << X[1][P[1]] << '\n';
        exit(0);
    }
    assert(k == 4);
    Rect I = universe_rect;
    for (Rect& r : rects)
        I = intersect(I, r);
    assert(I.c[0][1] < I.c[0][0]);
    assert(I.c[1][1] < I.c[1][0]);
    
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 528 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 520 KB Output is correct
9 Correct 4 ms 452 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 4 ms 548 KB Output is correct
12 Correct 4 ms 460 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 428 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 400 KB Output is correct
7 Correct 3 ms 416 KB Output is correct
8 Correct 5 ms 656 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 6 ms 656 KB Output is correct
12 Correct 5 ms 560 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Incorrect 5 ms 660 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 4 ms 424 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 331 ms 17604 KB Output is correct
6 Correct 377 ms 17616 KB Output is correct
7 Correct 390 ms 17612 KB Output is correct
8 Correct 372 ms 17620 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 456 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 338 ms 20676 KB Output is correct
6 Correct 353 ms 21064 KB Output is correct
7 Correct 361 ms 20420 KB Output is correct
8 Correct 382 ms 22240 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 528 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 520 KB Output is correct
9 Correct 4 ms 452 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 4 ms 548 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 376 ms 22464 KB Output is correct
14 Correct 339 ms 22088 KB Output is correct
15 Correct 339 ms 23060 KB Output is correct
16 Correct 372 ms 20424 KB Output is correct
17 Correct 362 ms 21592 KB Output is correct
18 Correct 324 ms 19732 KB Output is correct
19 Correct 361 ms 22092 KB Output is correct
20 Correct 395 ms 29432 KB Output is correct
21 Correct 338 ms 23520 KB Output is correct
22 Correct 354 ms 28720 KB Output is correct
23 Correct 370 ms 28484 KB Output is correct
24 Correct 384 ms 28048 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 428 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 400 KB Output is correct
7 Correct 3 ms 416 KB Output is correct
8 Correct 5 ms 656 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 6 ms 656 KB Output is correct
12 Correct 5 ms 560 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Incorrect 5 ms 660 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -