oj.uz

Submission #928084

# Submission time Handle Problem Language Result Execution time Memory
928084 2024-02-15T20:25:32 Z EJIC_B_KEDAX Carnival Tickets (IOI20_tickets) C++17
25 / 100
 540 ms 73244 KB 
#include <bits/stdc++.h>
#include "tickets.h"

using ll = long long;

using namespace std;

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;
            a[i].first += t[i][j];
        }
        // a[i].first = t[i][m - 1] + t[i][0];
    }
    for (int r = 0; r < k; r++) {
        vector<int> nw;
        sort(a.begin(), a.end());
        for (int i = 0; i < n / 2; i++) {
            a[i].first -= t[a[i].second][bg[a[i].second]];
            // a[i].first += t[a[i].second][bg[a[i].second] + 1];
            nw.push_back(t[a[i].second][bg[a[i].second]]);
            s[a[i].second][bg[a[i].second]++] = r;
        }
        for (int i = n / 2; i < n; i++) {
            a[i].first -= t[a[i].second][end[a[i].second]];
            // a[i].first += t[a[i].second][end[a[i].second] - 1];
            nw.push_back(t[a[i].second][end[a[i].second]]);
            s[a[i].second][end[a[i].second]--] = r;
        }
        for (int i : nw) {
            res += abs(i);
        }
        sort(nw.begin(), nw.end());
        assert(0 >= nw[n / 2 - 1] && 0 <= nw[n / 2]);
    }
    allocate_tickets(s);
    return res;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Contestant returned 2543298744 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
14.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 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 16 ms 2520 KB Output is correct
6 Correct 429 ms 54508 KB Output is correct
7 Correct 443 ms 54924 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 15 ms 2180 KB Output is correct
14 Correct 14 ms 2008 KB Output is correct
15 Correct 455 ms 53864 KB Output is correct

Subtask #4
0 / 14.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 344 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 25 ms 2520 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Runtime error 540 ms 73244 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 604 KB Contestant returned 38993572901 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 604 KB Contestant returned 38993572901 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Contestant returned 2543298744 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -