oj.uz

Submission #421975

# Submission time Handle Problem Language Result Execution time Memory
421975 2021-06-09T14:21:34 Z idk321 Carnival Tickets (IOI20_tickets) C++17
41 / 100
 952 ms 68420 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 296 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 588 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 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 32 ms 3152 KB Output is correct
6 Correct 844 ms 51464 KB Output is correct

Subtask #3
14.0 / 14.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 30 ms 3048 KB Output is correct
6 Correct 797 ms 64752 KB Output is correct
7 Correct 952 ms 65224 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 928 KB Output is correct
13 Correct 31 ms 2492 KB Output is correct
14 Correct 25 ms 2572 KB Output is correct
15 Correct 856 ms 68420 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 296 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 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 32 ms 3152 KB Output is correct
12 Correct 844 ms 51464 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 30 ms 3048 KB Output is correct
18 Correct 797 ms 64752 KB Output is correct
19 Correct 952 ms 65224 KB Output is correct
20 Correct 4 ms 588 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 8 ms 928 KB Output is correct
25 Correct 31 ms 2492 KB Output is correct
26 Correct 25 ms 2572 KB Output is correct
27 Correct 856 ms 68420 KB Output is correct
28 Incorrect 1 ms 296 KB WA in grader: failure to call allocate_tickets
29 Halted 0 ms 0 KB -