Submission #319295

#	Time	Username	Problem	Language	Result	Execution time	Memory
319295		northlake	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	114 ms	744 KiB

tickets

#include<tickets.h>
#include<bits/stdc++.h>
 
using namespace std;
 
int find_in_x(vector<vector<int>> x, int i, int v) {
    for (int j = 0; j < x[i].size(); j++) {
        if (x[i][j] == v) return j;
    }
}
 
long long find_maximum(int k, vector<vector<int>> x) {
    int n = x.size();
    vector<vector<int>> s {x};
    for (auto& e1 : s) {
        for (auto& e2 : e1) e2 = -1;
    }
 
    vector<pair<int,int>> min_values;
    vector<pair<int,int>> max_values;
    for (int i = 0; i < n; i++) {
        vector<int> el = x[i];
        int minx = pow(10,9);
        int maxx = 0;
        for (auto e : el) {
            minx = min(minx, e);
            maxx = max(maxx, e);
        }
        min_values.push_back(make_pair(minx, i));
        max_values.push_back(make_pair(maxx, i));
    }
    sort(min_values.begin(), min_values.end());
    sort(max_values.rbegin(), max_values.rend());
 
    vector<int> values;
    bool taken[n] = {false};
    for (int i = 0; i < n; i++) {
        pair<int,int> small = min_values[i];
        pair<int,int> big = max_values[i];
        if (taken[small.second] && taken[big.second]) {
            continue;
        }
        else if (taken[small.second]) {
            values.push_back(big.first);
            taken[big.second] = true;
            s[big.second][find_in_x(x, big.second, big.first)] = 0;
        }
        else if (taken[big.second]) {
            values.push_back(small.first);
            taken[small.second] = true;
            s[small.second][find_in_x(x, small.second, small.first)] = 0;
        }
        else if (small.second == big.second) {
            values.push_back(small.first);
            taken[small.second] = true;
            s[small.second][find_in_x(x, small.second, small.first)] = 0;
        }
        else {
            values.push_back(small.first);
            values.push_back(big.first);
            taken[big.second] = true;
            taken[small.second] = true;
            s[big.second][find_in_x(x, big.second, big.first)] = 0;
            s[small.second][find_in_x(x, small.second, small.first)] = 0;
        }
    }
    sort(values.begin(), values.end());
 
    int optimal_value = values[n/2];
    
    long long result = 0ll;
    for (auto el : x) {
        result += static_cast<long long>(abs(optimal_value-el[0]));
    }
 
    allocate_tickets(s);
    return result;
}

Compilation message (stderr)

tickets.cpp: In function 'int find_in_x(std::vector<std::vector<int> >, int, int)':
tickets.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int j = 0; j < x[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~
tickets.cpp:10:1: warning: control reaches end of non-void function [-Wreturn-type]
   10 | }
      | ^

• 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