Submission #316491

#	Time	Username	Problem	Language	Result	Execution time	Memory
316491		nikatamliani	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	1024 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define ll long long
const ll BIG = 1, SMALL = 2, oo = 1e9 + 10;
ll find_maximum(int k, vector < vector < int > > a) {
    int n = a.size(), m = a[0].size();
    vector < pair < int, int > > g;
    vector < vector < int > > L(n, vector < int >(0)), R(n, vector < int > (0));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            g.push_back({a[i][j], i});
        }
    }
    vector < bool > canTake(g.size(), 1);
    sort(g.begin(), g.end());
    ll sumL = 0, sumR = 0;
    for(int i = 0; i < k * n / 2; ++i) {
        canTake[i] = 0;
        sumL += g[i].first;
        L[g[i].second].push_back(i);
    }
    for(int i = g.size() - 1; i >= g.size() - k * n / 2; --i) {
        canTake[i] = 0;
        sumR += g[i].first;
        R[g[i].second].push_back(i);
    }
    for(int i = k * n / 2; i < g.size() - k * n / 2; ++i) {
        if(L[g[i].second].size() + R[g[i].second].size() < k) {
            canTake[i] = 1;
        }
    }
    int Lptr = 0, Rptr = g.size() - 1;
    vector < vector < int > > mark(n, vector < int > (m));
    for(int i = 0; i < n; ++i) {
        reverse(R[i].begin(), R[i].end());
        while(L[i].size() + R[i].size() > k) {
            while(Lptr < g.size() && canTake[Lptr] == 0) ++Lptr;
            while(Rptr >= 0 && canTake[Rptr] == 0) --Rptr;
            int deleteLeft = oo, deleteRight = oo;
            if(canTake[Lptr] == 1 && L[i].size()) {
                deleteLeft = g[Lptr].first - g[L[i].back()].first;
            }
            if(canTake[Rptr] == 1 && R[i].size()) {
                deleteRight = g[R[i].back()].first - g[Rptr].first;
            }
            if(deleteLeft < deleteRight) {
                L[i].pop_back();
                L[g[Lptr].second].push_back(Lptr);
                canTake[Lptr] = 0;
                sumL += deleteLeft;
            } else {
                R[i].pop_back();
                R[g[Rptr].second].push_back(Rptr);
                canTake[Rptr] = 0;
                sumR += deleteRight; 
            }
        }
    }
    vector < vector < int > > pL(n, vector < int > (0)), pR(n, vector < int > (0));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < L[i].size(); ++j) mark[i][j] = SMALL, pL[i].push_back(j);
        for(int j = 0; j < R[i].size(); ++j) mark[i][m - j - 1] = BIG, pR[i].push_back(m - j - 1);
    }
    vector < vector < int > > ans(n, vector < int > (m, -1));
    vector < vector < int > > f(n + 1, vector < int > (0));
    for(int i = 0; i < k; ++i) {
        for(int x = 0; x < n; ++x) {
            f[pL[x].size()].push_back(x);
        }
        int cnt = n / 2;
        vector < int > cur(n);
        for(int x = n; x >= 1; --x) {
            for(int pp : f[x]) {
                if(cnt == 0) break;
                cur[pp] = 1;
                --cnt;
            }
        }
        for(int x = 0; x < n; ++x) {
            if(cur[x]) {
                ans[x][pL[x].back()] = i;
                pL[x].pop_back();
            } else {
                ans[x][pR[x].back()] = i;
                pR[x].pop_back();
            }
        }
        for(int x = 0; x < n; ++x) {
            f[x].clear();
        }
    }
    // for(auto x : ans) {
    //     for(int i : x) cout << i << ' '; cout << '\n';
    // }
    allocate_tickets(ans);
    return sumR - sumL;
}
// int main() {
//     find_maximum(2, {{0, 2, 5}, {1, 1, 3}});
// }

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:23:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = g.size() - 1; i >= g.size() - k * n / 2; --i) {
      |                               ~~^~~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:28:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = k * n / 2; i < g.size() - k * n / 2; ++i) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:29:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         if(L[g[i].second].size() + R[g[i].second].size() < k) {
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
tickets.cpp:37:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         while(L[i].size() + R[i].size() > k) {
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
tickets.cpp:38:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             while(Lptr < g.size() && canTake[Lptr] == 0) ++Lptr;
      |                   ~~~~~^~~~~~~~~~
tickets.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = 0; j < L[i].size(); ++j) mark[i][j] = SMALL, pL[i].push_back(j);
      |                        ~~^~~~~~~~~~~~~
tickets.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < R[i].size(); ++j) mark[i][m - j - 1] = BIG, pR[i].push_back(m - j - 1);
      |                        ~~^~~~~~~~~~~~~

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