Submission #421975

#	Time	Username	Problem	Language	Result	Execution time	Memory
421975		idk321	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	952 ms	68420 KiB

tickets

#include "tickets.h"
#include <vector>

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

const ll INF = 1000000000000000000LL;

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));
    if (m == 1)
    {

        for (int i = 0; i < n; i++) answer[i][0] = 0;
        allocate_tickets(answer);
        vector<int> values(n);
        for (int i = 0; i < n; i++)
        {
            values[i] = x[i][0];
        }
        sort(values.begin(), values.end());

        ll res = 0;
        int mid = (0 + n - 1) / 2;
        for (int i = 0; i < n; i++)
        {
            res += abs(values[mid] - values[i]);
        }

        return res;
    }



    int big = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++) big = max(big, x[i][j]);
    }

    if (big <= 1)
    {
        int turn = 0;

        vector<vector<vector<int>>> isAt(n, vector<vector<int>>(2));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                isAt[i][x[i][j]].push_back(j);
            }
        }

        int res = 0;

        for (int a = 0; a < k; a++)
        {
            vector<array<int, 3>> byFreq;
            for (int i = 0; i < n; i++) byFreq.push_back({isAt[i][0].size(), isAt[i][1].size(), i});
            sort(byFreq.rbegin(), byFreq.rend());
            int f0 = 0;
            int f1 = 0;
            for (int i = 0; i < n / 2; i++)
            {
                int node = byFreq[i][2];
                if (!isAt[node][0].empty())
                {
                    answer[node][isAt[node][0].back()] = a;
                    isAt[node][0].pop_back();
                    f0++;
                } else
                {
                    answer[node][isAt[node][1].back()] = a;
                    isAt[node][1].pop_back();
                    f1++;
                }
            }
            for (int i = n / 2; i < n; i++)
            {
                int node = byFreq[i][2];
                if (!isAt[node][1].empty())
                {
                    answer[node][isAt[node][1].back()] = a;
                    isAt[node][1].pop_back();
                    f1++;
                } else
                {
                    answer[node][isAt[node][0].back()] = a;
                    isAt[node][0].pop_back();
                    f0++;
                }
            }

            res += min(f1, f0);
        }


        allocate_tickets(answer);

        return res;
    }


    if (k == 1)
    {
        ll res = -1;
        vector<int> resOrder(n);
        for (int a = 0;  a < 2 * n; a++)
        {
            int ai = a / 2;
            int val = x[ai].front();
            if (a % 2 == 1) val = x[ai].back();

            vector<int> order(n);
            order[ai] = (a % 2);
            ll cres = 0;
            int taken = 0;
            vector<array<int, 2>> poss;
            for (int i = 0; i < n; i++)
            {
                if (i == ai) continue;
                if (val < x[i].front())
                {
                    taken++;
                    cres += x[i].back() - val;
                    order[i] = 1;
                } else
                {
                    cres += val - x[i].front();
                    if (x[i].back() >= val)
                    {
                        poss.push_back({x[i].back() - val - (val - x[i].front()), i});
                    }
                }
            }

            sort(poss.rbegin(), poss.rend());
            for (int i = 0; i < poss.size() && taken < n / 2; i++)
            {

                order[poss[i][1]] = 1;
                cres += poss[i][0];
                taken++;
                if (taken == n / 2 - 1 || taken == n / 2)
                {

                    if (cres > res)
                    {
                        res = cres;
                        resOrder = order;
                    }
                }
            }

            if (taken == n / 2 - 1 || taken == n / 2)
            {

                if (cres > res)
                {
                    res = cres;
                    resOrder = order;
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            if (resOrder[i])
            {
                answer[i][m - 1] = 0;
            } else
            {
                answer[i][0] = 0;
            }
        }
        allocate_tickets(answer);
        return res;
    }



	return 1;
}

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

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:63:74: warning: narrowing conversion of '(&(& isAt.std::vector<std::vector<std::vector<int> > >::operator[](((std::vector<std::vector<std::vector<int> > >::size_type)i)))->std::vector<std::vector<int> >::operator[](0))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   63 |             for (int i = 0; i < n; i++) byFreq.push_back({isAt[i][0].size(), isAt[i][1].size(), i});
      |                                                           ~~~~~~~~~~~~~~~^~
tickets.cpp:63:93: warning: narrowing conversion of '(&(& isAt.std::vector<std::vector<std::vector<int> > >::operator[](((std::vector<std::vector<std::vector<int> > >::size_type)i)))->std::vector<std::vector<int> >::operator[](1))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   63 |             for (int i = 0; i < n; i++) byFreq.push_back({isAt[i][0].size(), isAt[i][1].size(), i});
      |                                                                              ~~~~~~~~~~~~~~~^~
tickets.cpp:47:13: warning: unused variable 'turn' [-Wunused-variable]
   47 |         int turn = 0;
      |             ^~~~
tickets.cpp:142:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             for (int i = 0; i < poss.size() && taken < n / 2; i++)
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10