oj.uz

Submission #300166

# Submission time Handle Problem Language Result Execution time Memory
300166 2020-09-16T22:06:40 Z model_code Carnival Tickets (IOI20_tickets) C++17
27 / 100
 860 ms 70728 KB 
// limli-greedy-ends
#include <bits/stdc++.h>

#include "tickets.h"
using namespace std;

typedef pair<int, int> ii;
typedef long long ll;

int n, s, k;

int magic[1510];
int cmp(int a, int b) {
    return magic[a] < magic[b];
}

long long find_maximum(int k1, vector<vector<int>> d) {
    k = k1;
    n = d.size();
    s = d[0].size();
    vector<vector<int>> answer;
    for (int i = 0; i < n; i++) {
        vector<int> row(s);
        for (int j = 0; j < s; j++) {
            row[j] = -1;
        }
        answer.push_back(row);
    }
    vector<deque<ii>> ticketsleft(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < s; j++) {
            ticketsleft[i].push_back(ii(d[i][j], j));
        }
        sort(ticketsleft[i].begin(), ticketsleft[i].end());
        magic[i] = ticketsleft[i][0].first + ticketsleft[i][s-1].first;
    }
    ll pipelength = 0;
    for (int day = 0; day < k; day++) {
        // printf("day %d\n", day);
        vector<int> order(n);
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        sort(order.begin(), order.end(), cmp);
        vector<int> stuff(n);
        for (int i = 0; i < n; i++) {
            int ind = order[i];
            ii ship = ii(-1,-1);
            if (i < n / 2) {
                ship = ticketsleft[ind].front();
                ticketsleft[ind].pop_front();
                if (!ticketsleft[ind].empty())
                    magic[ind] += ticketsleft[ind].front().first;
            } else {
                ship = ticketsleft[ind].back();
                ticketsleft[ind].pop_back();
                if (!ticketsleft[ind].empty())
                    magic[ind] += ticketsleft[ind].back().first;
            }
            // printf("company %d: %d %d\n", ind, ship.first, ship.second);
            stuff[ind] = ship.first;
            answer[ind][ship.second] = day;
            magic[ind] -= ship.first;
        }
        sort(stuff.begin(), stuff.end());
        int med = stuff[n / 2];
        for (int i = 0; i < n; i++) {
            pipelength += abs(stuff[i] - med);
        }
    }
    allocate_tickets(answer);
    return pipelength;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 54 ms 3288 KB Output is correct
6 Correct 860 ms 70728 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Contestant returned 5 while correct return value is 6.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 3 ms 1792 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 54 ms 3288 KB Output is correct
12 Correct 860 ms 70728 KB Output is correct
13 Incorrect 0 ms 256 KB Contestant returned 5 while correct return value is 6.
14 Halted 0 ms 0 KB -