oj.uz

Submission #422087

# Submission time Handle Problem Language Result Execution time Memory
422087 2021-06-09T17:23:58 Z idk321 Carnival Tickets (IOI20_tickets) C++14
16 / 100
 640 ms 60304 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;
        for (int j = m - 1, l = k - 1; l >= 0; l--, j--)
        {

            pq.push({l, j, i, x[i][j] + x[i][l]});
        }
    }

    vector<int> work(n, m);
    for (int i = 0; i < n * k / 2; i++)
    {
        auto cur = pq.top();
        pq.pop();
        res += cur[3];
        work[cur[2]] = min(work[cur[2]], cur[1]);


    }
    for (int i = 0; i < n; i++)
    {
        int toDel = m - work[i];
        for (int j = work[i]; j < m; j++)
        {
            type[i][j] = 1;
        }
        for (int j = k - 1; k -j <= toDel; j--)
        {
            type[i][j] = 0;
        }
    }

    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:93: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]
   93 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                               ~~~~~~~~~~~~~^~
tickets.cpp:93: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]
   93 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                                                ~~~~~~~~~~~^~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

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 2752 KB Output is correct
6 Correct 640 ms 60304 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -