Submission #303205

#	Time	Username	Problem	Language	Result	Execution time	Memory
303205		12tqian	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1501 ms	54776 KiB

tickets

#ifdef LOCAL
#else
#include "tickets.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL
void allocate_tickets(vector<vector<int>> s) {
    return;
}
#else
#endif

ll find_maximum(int k, vector<vector<int>> x) {
    const ll INF = 1e15;
    int n = x.size();
    int m = x[0].size();
    vector<vector<int>> res(n, vector<int>(m, -1));
    vector<int> lef(n);
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            lef[i] = k / 2;
        } else {
            lef[i] = k - k / 2;
        }
    }
    set<array<ll, 2>> shift_left;
    set<array<ll, 2>> shift_right;
    auto calc_right = [&](int id) -> ll {
        // you want to move something to minus
        if (lef[id] == k) {
            // never advantageous
            return INF;
        } else {
            // what you'll get
            int rig = k - lef[id];
            return x[id][lef[id]] + x[id][m - rig];
        }
    };
    auto calc_left = [&](int id) -> ll {
        // you want to move something to plus
        if (lef[id] == 0) {
            return -INF;
        } else {
            int rig = k - lef[id];
            return x[id][lef[id] - 1] + x[id][m - rig - 1];
        }
    };
    auto modify = [&](int id, int change) {
        ll l = calc_left(id);
        ll r = calc_right(id);
        shift_left.erase({l, id});
        shift_right.erase({r, id});
        lef[id] += change;
        l = calc_left(id);
        r = calc_right(id);
        shift_left.insert({l, id});
        shift_right.insert({r, id});
    };
    for (int i = 0; i < n; i++) {
        shift_left.insert({calc_left(i), i});
        shift_right.insert({calc_right(i), i});
    }
    while (*shift_right.begin() < *shift_left.rbegin()) {
        int add = (*shift_right.begin())[1];
        int sub = (*shift_left.rbegin())[1];
        modify(sub, -1);
        modify(add, 1);
    }
    ll ans = 0;
    vector<array<int, 3>> neg;
    vector<array<int, 3>> pos;
    vector<int> neg_filled(k);
    vector<int> pos_filled(k);
    set<pair<int, int>> diff;
    for (int i = 0; i < k; i++) {
        diff.emplace(0, i);
    }
    for (int i = 0; i < n; i++) {
        int l = lef[i];
        int r = k - lef[i];
        vector<pair<int, int>> L;
        vector<pair<int, int>> R;
        auto beg = diff.begin();
        auto fin = prev(diff.end());
        while (R.size() < r) {
            R.push_back(*beg);
            if (R.size() == r) {
                break;
            }
            beg = next(beg);
        }
        while (L.size() < l) {
            L.push_back(*fin);
            if (L.size() == l) {
                break;
            }
            fin = prev(fin);
        }
        auto change = [&](pair<int, int> x, int delta) {
            diff.erase(x);
            x.first += delta;
            diff.insert(x);
        };
        int it = 0;
        for (auto y: L) {
            change(y, -1);
            res[i][it] = y.second;
            ans -= x[i][it];
            it++;
        }
        it = m - 1;
        for (auto y: R) {
            change(y, 1);
            res[i][it] = y.second;
            ans += x[i][it];
            it--;
        }
    }
    allocate_tickets(res);
    return ans;

}
#ifdef LOCAL
int main() {
//    freopen("file.in", "r", stdin);
//    string line; cin >> line;
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> s(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> s[i][j];
        }
    }
    cout << find_maximum(k, s) << '\n';;
    return 0;
}
#else
#endif

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:99:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         while (R.size() < r) {
      |                ~~~~~~~~~^~~
tickets.cpp:101:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |             if (R.size() == r) {
      |                 ~~~~~~~~~^~~~
tickets.cpp:106:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |         while (L.size() < l) {
      |                ~~~~~~~~~^~~
tickets.cpp:108:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |             if (L.size() == l) {
      |                 ~~~~~~~~~^~~~

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