Submission #1077974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077974		anango	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	1510 ms	286768 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<signed>> intify(vector<vector<int>> res) {
    vector<vector<signed>> ans(res.size(),vector<signed>(res[0].size()));
    for (int i=0; i<res.size(); i++) {
        for (int j=0; j<res[0].size(); j++) {
            ans[i][j] = res[i][j];
        }
    }
    return ans;
}

long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> elems;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            elems.push_back({x[i][j],i,j});
        }
    }
    sort(elems.begin(), elems.end());
    vector<vector<int>> answer(n,vector<int>(m,-1));
    int mid = n*m/2;
    for (int i=0; i<mid; i++) {
        answer[elems[i][1]][elems[i][2]] = -2; //minus
    }
    int sol = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (answer[i][j]==-1) {
                sol+=x[i][j];
            }
            else {
                sol-=x[i][j];
            }
        }
    }
    //-1 is plus, -2 is minus
    vector<set<int>> minus_rem(n); vector<set<int>> plus_rem(n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (answer[i][j]==-1) {
                plus_rem[i].insert(j);
            }
            else {
                minus_rem[i].insert(j);
            }
        }
    }
    for (int op=0; op<m; op++) {
        int balance = 0;
        set<int> rem;
        for (int i=0; i<n; i++) {
            if (!plus_rem[i].size()) {
                answer[i][*minus_rem[i].begin()] = op;
                minus_rem[i].erase(minus_rem[i].begin());
                balance--;
            }
            else if (!minus_rem[i].size()) {
                answer[i][*plus_rem[i].begin()] = op;
                plus_rem[i].erase(plus_rem[i].begin());
                balance++;
            }
            else {
                rem.insert(i);
            }
        }
        for (int i:rem) {
            if (balance>=0) {
                answer[i][*minus_rem[i].begin()] = op;
                minus_rem[i].erase(minus_rem[i].begin());
                balance--;
            }
            else {
                answer[i][*plus_rem[i].begin()] = op;
                plus_rem[i].erase(plus_rem[i].begin());
                balance++;
            }
        }
    }

	allocate_tickets(intify(answer));
	return sol;
}

Compilation message (stderr)

tickets.cpp: In function 'std::vector<std::vector<int> > intify(std::vector<std::vector<long long int> >)':
tickets.cpp:9:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<res.size(); i++) {
      |                   ~^~~~~~~~~~~
tickets.cpp:10:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for (int j=0; j<res[0].size(); j++) {
      |                       ~^~~~~~~~~~~~~~

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