oj.uz

Submission #422101

# Submission time Handle Problem Language Result Execution time Memory
422101 2021-06-09T17:36:04 Z idk321 Carnival Tickets (IOI20_tickets) C++17
27 / 100
 627 ms 60348 KB 
#include "tickets.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1000000000000000000LL;

struct Comp
{
    bool operator() (const array<int, 4>& ar1, const array<int, 4>& ar2) const
    {
        return ar1[3] < ar2[3];
    }
};

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer;
    answer.resize(n, vector<int>(m, -1));



    priority_queue<array<int, 4>, vector<array<int, 4>>, Comp> pq;
    vector<vector<int>> type(n, vector<int>(m));
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            res -= x[i][j];
            type[i][j] = -1;
        }
        ll sum = 0;

        pq.push({0, m - 1, i, x[i][0] + x[i][m - 1]});
    }

    for (int i = 0; i < n * k / 2; i++)
    {
        auto cur = pq.top();
        pq.pop();
        res += cur[3];
        type[cur[2]][cur[0]] = 0;
        type[cur[2]][cur[1]] = 1;
        if (cur[0] != 0 && type[cur[2]][cur[0] - 1] == -1)
        {
            pq.push({cur[0] - 1, cur[1] - 1, cur[2], x[cur[2]][cur[1] - 1] + x[cur[2]][cur[0] - 1]});
        }
    }

    vector<vector<int>> small(n);
    vector<vector<int>> big(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (type[i][j] == -1) small[i].push_back(j);
            if (type[i][j] == 1) big[i].push_back(j);
        }
    }


    ll sumSmall = 0;
    ll sumBig =0;
    for (int i = 0; i < n; i++)
    {
        sumSmall += small[i].size();
        sumBig += big[i].size();
    }


    for (int a = 0; a < k; a++)
    {
        vector<array<int, 3>> byFreq;
        for (int i = 0; i < n; i++)
        {
            byFreq.push_back({small[i].size(), big[i].size(), i});
        }
        sort(byFreq.rbegin(), byFreq.rend());
        for (int i = 0; i < n / 2; i++)
        {
            int y = byFreq[i][2];
            answer[y][small[y].back()] = a;
            small[y].pop_back();
        }
        for (int i = n / 2; i < n; i++)
        {
            int y = byFreq[i][2];

            answer[y][big[y].back()] = a;
            big[y].pop_back();
        }
    }

    allocate_tickets(answer);
	return res;
}

/*
5 3 1
1 8 1000
1 3 4
3 5 6
2 5 7
1 5 10
*/

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:36:12: warning: unused variable 'sum' [-Wunused-variable]
   36 |         ll sum = 0;
      |            ^~~
tickets.cpp:80:44: warning: narrowing conversion of '(& small.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                               ~~~~~~~~~~~~~^~
tickets.cpp:80:59: warning: narrowing conversion of '(& big.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                                                ~~~~~~~~~~~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 844 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 27 ms 2756 KB Output is correct
6 Correct 627 ms 60348 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 2 but the tickets gives a total value of 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 but the tickets gives a total value of -10
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 but the tickets gives a total value of -10
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 but the tickets gives a total value of -10
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 27 ms 2756 KB Output is correct
12 Correct 627 ms 60348 KB Output is correct
13 Incorrect 1 ms 204 KB Contestant returned 2 but the tickets gives a total value of 0
14 Halted 0 ms 0 KB -