oj.uz

Submission #958297

# Submission time Handle Problem Language Result Execution time Memory
958297 2024-04-05T10:34:56 Z Vladth11 Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 20436 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 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 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 13 ms 2396 KB Output is correct
2 Correct 5 ms 2648 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2392 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Correct 6 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2420 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2516 KB Output is correct
9 Correct 38 ms 2644 KB Output is correct
10 Correct 489 ms 2528 KB Output is correct
11 Correct 32 ms 2392 KB Output is correct
12 Correct 109 ms 2644 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 5 ms 2552 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 8 ms 2548 KB Output is correct
6 Correct 5 ms 2548 KB Output is correct
7 Correct 633 ms 2520 KB Output is correct
8 Correct 79 ms 2396 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 143 ms 2392 KB Output is correct
11 Correct 2345 ms 2524 KB Output is correct
12 Correct 24 ms 2396 KB Output is correct
13 Correct 27 ms 2548 KB Output is correct
14 Correct 1673 ms 2608 KB Output is correct
15 Correct 42 ms 2600 KB Output is correct
16 Correct 1237 ms 2644 KB Output is correct
17 Correct 179 ms 2396 KB Output is correct
18 Correct 228 ms 2392 KB Output is correct
19 Correct 541 ms 2396 KB Output is correct
20 Execution timed out 3021 ms 2392 KB Time limit exceeded
21 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 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 69 ms 10704 KB Output is correct
6 Correct 66 ms 10824 KB Output is correct
7 Correct 73 ms 10704 KB Output is correct
8 Correct 66 ms 10704 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2396 KB Output is correct
2 Correct 5 ms 2648 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 277 ms 12280 KB Output is correct
6 Execution timed out 3021 ms 20436 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2392 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Correct 6 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2420 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2516 KB Output is correct
9 Correct 38 ms 2644 KB Output is correct
10 Correct 489 ms 2528 KB Output is correct
11 Correct 32 ms 2392 KB Output is correct
12 Correct 109 ms 2644 KB Output is correct
13 Correct 1970 ms 13336 KB Output is correct
14 Execution timed out 3048 ms 12348 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 5 ms 2552 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 8 ms 2548 KB Output is correct
6 Correct 5 ms 2548 KB Output is correct
7 Correct 633 ms 2520 KB Output is correct
8 Correct 79 ms 2396 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 143 ms 2392 KB Output is correct
11 Correct 2345 ms 2524 KB Output is correct
12 Correct 24 ms 2396 KB Output is correct
13 Correct 27 ms 2548 KB Output is correct
14 Correct 1673 ms 2608 KB Output is correct
15 Correct 42 ms 2600 KB Output is correct
16 Correct 1237 ms 2644 KB Output is correct
17 Correct 179 ms 2396 KB Output is correct
18 Correct 228 ms 2392 KB Output is correct
19 Correct 541 ms 2396 KB Output is correct
20 Execution timed out 3021 ms 2392 KB Time limit exceeded
21 Halted 0 ms 0 KB -