oj.uz

Submission #958301

# Submission time Handle Problem Language Result Execution time Memory
958301 2024-04-05T10:45:26 Z Vladth11 Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 14172 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);
    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;
    }
    vector <int> qq;
    for(i = 1; i <= n; i++) {
        qq.push_back(i);
    }
    while(1) {
        for(int j = 1; j <= k; j++) {
            buckets[j] = {0, 0, INF, INF};
        }
        vector <int> buni;
        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++;
                  break;
                }
            }
            buckets[care] = combine(q[acum], buckets[care]);
            if(oke){
                cnt++;
                buni.push_back(acum);
            } else {
                qq.push_back(acum);
                random_shuffle(qq.begin(), qq.end());
                break;
            }
        }
        for(auto x : qq){
            buni.push_back(x);
        }
        qq = buni;
        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 2392 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 2 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct

Subtask #3
3.0 / 3.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 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 27 ms 2648 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 9 ms 2568 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 14 ms 2568 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 2396 KB Output is correct
3 Correct 4 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 5 ms 2520 KB Output is correct
8 Correct 69 ms 2396 KB Output is correct
9 Correct 217 ms 2544 KB Output is correct
10 Correct 369 ms 2540 KB Output is correct
11 Correct 205 ms 2544 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct
13 Correct 39 ms 2396 KB Output is correct
14 Correct 284 ms 2540 KB Output is correct
15 Correct 8 ms 2396 KB Output is correct
16 Correct 723 ms 2536 KB Output is correct
17 Correct 30 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2560 KB Output is correct
20 Correct 889 ms 2540 KB Output is correct
21 Correct 224 ms 2392 KB Output is correct
22 Correct 15 ms 2396 KB Output is correct
23 Correct 1809 ms 2540 KB Output is correct
24 Correct 6 ms 2396 KB Output is correct
25 Correct 42 ms 2396 KB Output is correct
26 Correct 47 ms 2648 KB Output is correct
27 Correct 23 ms 2572 KB Output is correct
28 Correct 125 ms 2392 KB Output is correct
29 Correct 264 ms 2540 KB Output is correct
30 Correct 43 ms 2644 KB Output is correct
31 Correct 687 ms 2392 KB Output is correct
32 Correct 120 ms 2540 KB Output is correct
33 Correct 247 ms 2648 KB Output is correct
34 Correct 102 ms 2540 KB Output is correct
35 Correct 578 ms 2540 KB Output is correct
36 Execution timed out 3058 ms 2396 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 65 ms 13124 KB Output is correct
6 Correct 65 ms 13124 KB Output is correct
7 Correct 64 ms 13112 KB Output is correct
8 Correct 67 ms 13116 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 930 ms 13968 KB Output is correct
6 Execution timed out 3010 ms 14080 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.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 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 27 ms 2648 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 9 ms 2568 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 14 ms 2568 KB Output is correct
13 Execution timed out 3037 ms 14172 KB Time limit exceeded
14 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 2396 KB Output is correct
3 Correct 4 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 5 ms 2520 KB Output is correct
8 Correct 69 ms 2396 KB Output is correct
9 Correct 217 ms 2544 KB Output is correct
10 Correct 369 ms 2540 KB Output is correct
11 Correct 205 ms 2544 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct
13 Correct 39 ms 2396 KB Output is correct
14 Correct 284 ms 2540 KB Output is correct
15 Correct 8 ms 2396 KB Output is correct
16 Correct 723 ms 2536 KB Output is correct
17 Correct 30 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2560 KB Output is correct
20 Correct 889 ms 2540 KB Output is correct
21 Correct 224 ms 2392 KB Output is correct
22 Correct 15 ms 2396 KB Output is correct
23 Correct 1809 ms 2540 KB Output is correct
24 Correct 6 ms 2396 KB Output is correct
25 Correct 42 ms 2396 KB Output is correct
26 Correct 47 ms 2648 KB Output is correct
27 Correct 23 ms 2572 KB Output is correct
28 Correct 125 ms 2392 KB Output is correct
29 Correct 264 ms 2540 KB Output is correct
30 Correct 43 ms 2644 KB Output is correct
31 Correct 687 ms 2392 KB Output is correct
32 Correct 120 ms 2540 KB Output is correct
33 Correct 247 ms 2648 KB Output is correct
34 Correct 102 ms 2540 KB Output is correct
35 Correct 578 ms 2540 KB Output is correct
36 Execution timed out 3058 ms 2396 KB Time limit exceeded
37 Halted 0 ms 0 KB -