oj.uz

Submission #1050307

# Submission time Handle Problem Language Result Execution time Memory
1050307 2024-08-09T08:38:15 Z dozer Carnival Tickets (IOI20_tickets) C++14
27 / 100
 276 ms 60240 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define N 200005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;



long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n = x.size();
    int m = x[0].size();
    std::vector<std::vector<int>> answer(n, vector<int>(m, -1));
    vector<vector<int>> done(n, vector<int>(m, 0));
    long long ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < k; j++) {
            ans -= x[i][j];
            done[i][j] = 1;
        }
    }

    vector<array<int, 3>> v;
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= k; j++){
            int curr = m - j;
            int bk = k - j;
            v.pb({x[i][curr] + x[i][bk], i, curr});
        }
    }

    sort(v.rbegin(), v.rend());
    for (int i = 0; i < n * k / 2; i++){
        array<int, 3> curr = v[i];
        ans += curr[0];
        int bk = k - (m - curr[2]);
        done[curr[1]][bk] = 0;
        done[curr[1]][curr[2]] = 2;
    }

    vector<int> fpos(n, 0), bpos(n, m - 1);

    for (int i = 0; i < k; i++){
        vector<int> vis(n, 0);
        int sum = n / 2;
        for (int j = 0; j < n; j++){
            if (vis[j] == 0 && sum > 0 && fpos[j] < m && done[j][fpos[j]] == 1){
                vis[j] = 1;
                answer[j][fpos[j]] = i;
                fpos[j]++;
                sum--;
            }
        }
        sum = n / 2;
        for (int j = 0; j < n; j++){
            if (vis[j] == 0 && sum > 0 && bpos[j] >= 0 && done[j][bpos[j]] == 2){
                vis[j] = 1;
                answer[j][bpos[j]] = i;
                bpos[j]--;
                sum--;
            }
        }
    }
    allocate_tickets(answer);
    return ans;
}
/*
static int n;
static int m;
static int k;
static std::vector<std::vector<int>> d;
static std::vector<std::vector<int>> x;
static int called = 0;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        exit(0);
    }
}


void allocate_tickets( std::vector<std::vector<int>> _d) {
    check(!called, "allocate_tickets called more than once");
    d = _d;
    check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
    for (int i = 0; i < n; i++) {
        check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
    }
    called = 1;
}

int main() {
    fileio();
    assert(scanf("%d %d %d", &n, &m, &k) == 3);
    x.resize(n);
    for (int i = 0; i < n; i++) {
        x[i].resize(m);
        for (int j=0; j < m; j++) {
            assert(scanf("%d", &x[i][j]) == 1);
        }
    }
    fclose(stdin);

    long long answer = find_maximum(k, x);
    check(called, "failure to call allocate_tickets");
    printf("%lld\n", answer);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j) printf(" ");
            printf("%d", d[i][j]);
        }
        printf("\n");
    }
    fclose(stdout);
    return 0;
}
*/

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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct

Subtask #2
16.0 / 16.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 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 11 ms 2652 KB Output is correct
6 Correct 276 ms 60240 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB There is no ticket of color 2 on day 2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB There is no ticket of color 5 on day 7
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB There is no ticket of color 40 on day 4
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB There is no ticket of color 40 on day 4
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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 11 ms 2652 KB Output is correct
12 Correct 276 ms 60240 KB Output is correct
13 Incorrect 0 ms 348 KB There is no ticket of color 2 on day 2
14 Halted 0 ms 0 KB -