oj.uz

Submission #928149

# Submission time Handle Problem Language Result Execution time Memory
928149 2024-02-15T21:57:39 Z EJIC_B_KEDAX Carnival Tickets (IOI20_tickets) C++17
25 / 100
 571 ms 55208 KB 
#include <bits/stdc++.h>
#include "tickets.h"

using ll = long long;

using namespace std;

mt19937_64 mt(time(nullptr));

ll find_maximum(int k, vector<vector<int>> t) {
    int n = t.size(), m = t[0].size();
    vector<int> all;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            all.push_back(t[i][j]);
        }
    }
    sort(all.begin(), all.end());
    int middle = all[all.size() / 2];
    ll res = 0;
    vector<pair<ll, int>> a(n);
    vector<int> bg(n, 0), end(n, m - 1);
    vector<vector<int>> s(n, vector<int>(m, -1));
    for (int i = 0; i < n; i++) {
        a[i].first = 0;
        a[i].second = i;
        for (int j = 0; j < m; j++) {
            t[i][j] -= middle;
        }
    }
    int bgs = 0, ends = 0;
    for (int i = 0; i < n; i++) {
        for (int st = 0; st < k; st++) {
            if ((abs(t[i][bg[i]]) > abs(t[i][end[i]]) && t[i][bg[i]] <= 0) || t[i][end[i]] < 0) {
                bgs++;
                bg[i]++;
            } else {
                ends++;
                end[i]--;
            }
        }
    }
    if (bgs > ends) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = bg[i] - 1; j >= 0; j--) {
                int sw = end[i] - bg[i] - j - 1;
                if (t[i][sw] >= 0) {
                    st.emplace(-t[i][j] - t[i][sw], i);
                }
            }
        }
        while (bgs > ends) {
            assert(!st.empty());
            bgs--;
            ends++;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]--;
            end[i]--;
        }
    } else if (ends > bgs) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = end[i] + 1; j < m; j++) {
                int sw = bg[i] + j - end[i] - 1;
                if (t[i][sw] <= 0) {
                    st.emplace(t[i][j] + t[i][sw], i);
                }
            }
        }
        while (bgs < ends) {
            assert(!st.empty());
            bgs++;
            ends--;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]++;
            end[i]++;
        }
    }
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = bg[i];
        r[i] = m - end[i] - 1;
        for (int j = 0; j < l[i]; j++) {
            res += abs(t[i][j]);
        }
        for (int j = 0; j < r[i]; j++) {
            res += abs(t[i][m - j - 1]);
        }
    }
    for (int st = 0; st < k; st++) {
        vector<int> used(n, 0);
        int bal = 0;
        for (int i = 0; i < n; i++) {
            if (l[i] == k - st) {
                used[i] = 1;
                l[i]--;
                s[i][l[i]] = st;
                bal--;
            }
            if (r[i] == k - st) {
                used[i] = 1;
                s[i][m - r[i]] = st;
                r[i]--;
                bal++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (bal > 0) {
                    used[i] = 1;
                    l[i]--;
                    s[i][l[i]] = st;
                    bal--;
                } else {
                    used[i] = 1;
                    s[i][m - r[i]] = st;
                    r[i]--;
                    bal++;
                }
            }
        }
    }
    allocate_tickets(s);
    return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 856 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Incorrect 21 ms 2620 KB Contestant returned 149430668624 while correct return value is 149536936027.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 22 ms 2520 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 571 ms 54748 KB Output is correct
9 Correct 522 ms 50888 KB Output is correct
10 Correct 512 ms 50632 KB Output is correct
11 Correct 540 ms 55208 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Incorrect 2 ms 604 KB Contestant returned 191491640711 while correct return value is 191909121109.
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Incorrect 2 ms 604 KB Contestant returned 191491640711 while correct return value is 191909121109.
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Incorrect 21 ms 2620 KB Contestant returned 149430668624 while correct return value is 149536936027.
12 Halted 0 ms 0 KB -