oj.uz

답안 #422076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422076 2021-06-09T17:08:46 Z idk321 카니발 티켓 (IOI20_tickets) C++17
76 / 100
 1551 ms 103292 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;
        }
        for (int j = m - 1, l = k - 1; l >= 0; l--, j--)
        {
            pq.push({l, j, i, x[i][j] + x[i][l]});
        }
    }

    for (int i = 0; i < n * k / 2; i++)
    {
        auto cur = pq.top();
        pq.pop();
        res += cur[3];
        if (type[cur[2]][cur[0]] == -1)type[cur[2]][cur[0]] = 0;
        type[cur[2]][cur[1]] = 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:78: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]
   78 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                               ~~~~~~~~~~~~~^~
tickets.cpp:78: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]
   78 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                                                ~~~~~~~~~~~^~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 288 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 844 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 29 ms 3524 KB Output is correct
6 Correct 617 ms 60640 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 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 3648 KB Output is correct
6 Correct 820 ms 78648 KB Output is correct
7 Correct 908 ms 87556 KB Output is correct
8 Correct 5 ms 844 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 Runtime error 7 ms 1868 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 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 4 ms 588 KB Output is correct
5 Correct 50 ms 5360 KB Output is correct
6 Correct 7 ms 1104 KB Output is correct
7 Correct 9 ms 1452 KB Output is correct
8 Correct 1551 ms 103292 KB Output is correct
9 Correct 1411 ms 101048 KB Output is correct
10 Correct 1426 ms 100844 KB Output is correct
11 Correct 1529 ms 103132 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 560 KB Output is correct
12 Correct 3 ms 588 KB Output is correct

Subtask #6
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 560 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 26 ms 3600 KB Output is correct
14 Correct 27 ms 3628 KB Output is correct
15 Correct 36 ms 4288 KB Output is correct
16 Correct 46 ms 5320 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 34 ms 3992 KB Output is correct
21 Correct 37 ms 4364 KB Output is correct
22 Correct 39 ms 4504 KB Output is correct
23 Correct 43 ms 4868 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 288 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 29 ms 3524 KB Output is correct
12 Correct 617 ms 60640 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 3648 KB Output is correct
18 Correct 820 ms 78648 KB Output is correct
19 Correct 908 ms 87556 KB Output is correct
20 Correct 5 ms 844 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 Runtime error 7 ms 1868 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -