oj.uz

Submission #958296

# Submission time Handle Problem Language Result Execution time Memory
958296 2024-04-05T10:34:04 Z Vladth11 Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 20272 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 = 1000001;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

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

rect buckets[11];
int last[NMAX];

rect combine(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;
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    int n, i, k;
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        cin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2;
    }
    while(1) {
        for(int j = 1; j <= k; j++) {
            buckets[j] = {0, 0, INF, INF};
        }
        vector <int> qq;
        for(i = 1; i <= n; i++) {
            qq.push_back(i);
        }
        random_shuffle(qq.begin(), qq.end());
        int cnt = 0;
        while(qq.size()) {
            int acum = qq.back();
            qq.pop_back();
            int oke = 0;
            int care = 0;
            for(int j = 1; j <= k; j++) {
                rect inters = combine(q[acum], buckets[j]);
                if(inters.x1 <= inters.x2 && inters.y1 <= inters.y2) {
                    care = j;
                    oke++;
                }
            }
            buckets[care] = combine(q[acum], buckets[care]);
            if(oke) cnt++;
        }
        if(cnt == n) {
            for(i = 1; i <= k; i++) {
                cout << buckets[i].x1 << " " << buckets[i].y1 << "\n";
            }
            return 0;
        }
    }
    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 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2588 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 6 ms 2396 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 5 ms 2628 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 121 ms 2600 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Correct 87 ms 2640 KB Output is correct
11 Correct 64 ms 2600 KB Output is correct
12 Correct 29 ms 2396 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 21 ms 2392 KB Output is correct
4 Correct 7 ms 2628 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 3 ms 2584 KB Output is correct
7 Correct 63 ms 2396 KB Output is correct
8 Correct 277 ms 2396 KB Output is correct
9 Correct 380 ms 2644 KB Output is correct
10 Correct 1105 ms 2640 KB Output is correct
11 Correct 114 ms 2396 KB Output is correct
12 Correct 10 ms 2392 KB Output is correct
13 Execution timed out 3061 ms 2396 KB Time limit exceeded
14 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 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 78 ms 15128 KB Output is correct
6 Correct 74 ms 15040 KB Output is correct
7 Correct 86 ms 15312 KB Output is correct
8 Correct 72 ms 15104 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2588 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 6 ms 2396 KB Output is correct
5 Execution timed out 3067 ms 17044 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 5 ms 2628 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 121 ms 2600 KB Output is correct
9 Correct 6 ms 2392 KB Output is correct
10 Correct 87 ms 2640 KB Output is correct
11 Correct 64 ms 2600 KB Output is correct
12 Correct 29 ms 2396 KB Output is correct
13 Correct 984 ms 20272 KB Output is correct
14 Correct 1225 ms 20032 KB Output is correct
15 Execution timed out 3027 ms 20036 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 21 ms 2392 KB Output is correct
4 Correct 7 ms 2628 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 3 ms 2584 KB Output is correct
7 Correct 63 ms 2396 KB Output is correct
8 Correct 277 ms 2396 KB Output is correct
9 Correct 380 ms 2644 KB Output is correct
10 Correct 1105 ms 2640 KB Output is correct
11 Correct 114 ms 2396 KB Output is correct
12 Correct 10 ms 2392 KB Output is correct
13 Execution timed out 3061 ms 2396 KB Time limit exceeded
14 Halted 0 ms 0 KB -