oj.uz

Submission #894729

# Submission time Handle Problem Language Result Execution time Memory
894729 2023-12-28T20:13:53 Z box Hamburg Steak (JOI20_hamburg) C++17
11 / 100
 2 ms 856 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 2e3;

int N, K;
// int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
ar<int, 4> V[MAXN];
int order[MAXN], __[MAXN];
vector<int> breaks;
bool done[MAXN];
// vector<int> X, Y;
ar<int, 2> solutions[4];

ar<int, 4> operator+(const ar<int, 4> one, const ar<int, 4> two) {
    if (one[0] == -1 || two[0] == -1 || max(one[0], two[0]) > min(one[1], two[1]) || max(one[2], two[2]) > min(one[3], two[3])) return {-1, -1, -1, -1};
    return {max(one[0], two[0]), min(one[1], two[1]), max(one[2], two[2]), min(one[3], two[3])};
}

mt19937 rng(1234);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int l, r, u, d;
        cin >> l >> d >> r >> u;
        V[i] = {l, r, d, u};
        // cin >> L[i] >> R[i] >> U[i] >> D[i];
        /*
        X.push_back(L[i]);
        X.push_back(R[i]);
        Y.push_back(U[i]);
        Y.push_back(D[i]);
        */
        order[i] = i;
    }
    /*
    sort(begin(X), end(X));
    X.erase(unique(begin(X), end(X)), end(X));
    sort(begin(Y), end(Y));
    Y.erase(unique(begin(Y), end(Y)), end(Y));
    */
    for (int i = 0; i < N; i++) swap(order[i], order[rng() % (i + 1)]);
    while (1) {
        fill(done, done + N, false);
        int i = 0;
        for (int rep = 0; rep < K; rep++) {
            while (i < N && done[i]) i++;
            if (i == N) {
                while (rep < K)
                    solutions[rep++] = {1, 1};
                break;
            }
            done[i] = 1;
            auto v = V[order[i]];
            for (int j = i + 1; j < N; j++) if (!done[j] && (v + V[order[j]])[0] != -1) {
                v = v + V[order[j]];
                done[j] = 1;
            }
            solutions[rep] = {v[0], v[2]};
        }
        if (!count(done, done + N, false)) {
            for (int i = 0; i < K; i++)
                cout << solutions[i][0] << " " << solutions[i][1] << '\n';
            break;
        } else {
            int s = 0;
            for (int i = 0; i < N; i++) if (!done[i]) __[s++] = order[i];
            for (int i = 0; i < s; i++) swap(__[i], __[rng() % (i + 1)]);
            for (int i = 0; i < N; i++) if (done[i]) __[s++] = order[i];
            swap(order, __);
        }
    }
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 484 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 568 KB Output is correct
21 Correct 1 ms 544 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 2 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 2 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 344 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 2 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 484 KB Output is correct
58 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 484 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 568 KB Output is correct
21 Correct 1 ms 544 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 2 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 2 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 344 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 2 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 484 KB Output is correct
58 Correct 1 ms 348 KB Output is correct
59 Runtime error 2 ms 856 KB Execution killed with signal 11
60 Halted 0 ms 0 KB -