oj.uz

Submission #894730

# Submission time Handle Problem Language Result Execution time Memory
894730 2023-12-28T20:14:24 Z box Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 3000 ms 12344 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 = 2e5;
 
int N, K;
// int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
ar<int, 4> V[MAXN];
int order[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));
    */
    while (1) {
        for (int i = 0; i < N; i++) swap(order[i], order[rng() % (i + 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;
        }
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 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 2528 KB Output is correct

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 6 ms 2392 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 395 ms 2504 KB Output is correct
11 Correct 11 ms 2396 KB Output is correct
12 Correct 29 ms 2392 KB Output is correct

Subtask #4
0 / 6.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 2 ms 2396 KB Output is correct
4 Correct 9 ms 2396 KB Output is correct
5 Correct 8 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 80 ms 2396 KB Output is correct
8 Correct 47 ms 2396 KB Output is correct
9 Correct 39 ms 2648 KB Output is correct
10 Correct 48 ms 2396 KB Output is correct
11 Correct 2011 ms 2504 KB Output is correct
12 Correct 4 ms 2604 KB Output is correct
13 Execution timed out 3052 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 2 ms 2648 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 2528 KB Output is correct
5 Correct 63 ms 11860 KB Output is correct
6 Correct 69 ms 12272 KB Output is correct
7 Correct 69 ms 12088 KB Output is correct
8 Correct 65 ms 12228 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 1 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 110 ms 11976 KB Output is correct
6 Execution timed out 3018 ms 12248 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 6 ms 2392 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 395 ms 2504 KB Output is correct
11 Correct 11 ms 2396 KB Output is correct
12 Correct 29 ms 2392 KB Output is correct
13 Correct 850 ms 12056 KB Output is correct
14 Correct 2523 ms 12296 KB Output is correct
15 Correct 935 ms 12344 KB Output is correct
16 Execution timed out 3040 ms 12124 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #8
0 / 79.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 2 ms 2396 KB Output is correct
4 Correct 9 ms 2396 KB Output is correct
5 Correct 8 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 80 ms 2396 KB Output is correct
8 Correct 47 ms 2396 KB Output is correct
9 Correct 39 ms 2648 KB Output is correct
10 Correct 48 ms 2396 KB Output is correct
11 Correct 2011 ms 2504 KB Output is correct
12 Correct 4 ms 2604 KB Output is correct
13 Execution timed out 3052 ms 2396 KB Time limit exceeded
14 Halted 0 ms 0 KB -