Submission #808476

#	Time	Username	Problem	Language	Result	Execution time	Memory
808476		drdilyor	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	340 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
using ll = long long;
const int inf = 1e9;

#ifdef ONPC
#define debug(args...) {cout << "[" << #args << "]: "; debug_out(args);}
#else
#define debug(args...) {42;}
#endif

void debug_out() {
    cout << endl;
}
template<typename H, typename... T>
void debug_out(vector<H> h, T... t) {
    cout << "{";
    for (H i : h) cout << i << ", ";
    cout << "}, ";
    debug_out(t...);
}
template<typename H, typename... T>
void debug_out(H h, T... t) {
    cout << h << ", ";
    debug_out(t...);
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
    vector<tuple<int,int,int>> pos(n);
    for (int i = 0; i < n; i++)
        pos[i] = {-x[i][0], x[i][m-1], i};

    sort(pos.begin(), pos.end(), [&](auto a, auto b) {
            return get<1>(a) - get<0>(a) > get<1>(b) - get<0>(b);
    });

    int space = m - k;
    vector score(n, vector<ll>());
    for (int i = 0; i < n; i++) {
        ll cur = accumulate(x[i].begin(), x[i].end(), 0ll);
        ll base = cur;
        if (!space) score[i].push_back(0);
        for (int j = 0; j < m; j++) {
            cur -= x[i][j];
            if (j >= space) {
                cur += -x[i][j - space];
            }
            if (j >= space-1) {
                ll prev = score[i].size() ? score[i].back() : cur - base;
                score[i].push_back(cur - base - prev);
            }
        }
        assert((int)score[i].size() == k + 1);
        debug(i, score[i]);
    }

    vector<int> use(n);
    vector<array<int, 2>> left(n, {{}});
    int c0 = 0, c1 = 0;
    for (int i = 0; i < n; i++) {
        use[i] = k;
        for (int j = 0; j < k; j++) {
            if (x[i][j]) {
                c1++;
            } else c0++;
        }
        for (int j = k; j < m; j++) {
            left[i][x[i][j]]++;
        }
    }
    debug(c1, use);

    int good = n / 2 * k;
    for (int i = 0; i < n; i++) {
        debug(c1, i, use);
        while (c1 < good && use[i]) {
            c1 += x[i][m - 1 - k + use[i]];
            use[i]--;
        }
        debug(c1, i, use);
    }

    int rem = good;

    vector type(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < use[i]; j++) {
            if (x[i][j] == 1 && rem) {
                rem--;
                type[i][j] = 1;
            }
        }
        for (int j = 0; j < k - use[i]; j++) {
            if (x[i][j] == 1 && rem) {
                rem--;
                rbegin(type[i])[j] = 1;
            }
        }
        debug(i, type[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < use[i]; j++) {
            if (type[i][j]) continue;
            if (rem) {
                rem--;
                type[i][j] = 1;
            }
            else type[i][j] = -1;
        }
        for (int j = 0; j < k - use[i]; j++) {
            if (rbegin(type[i])[j]) continue;
            if (rem) {
                rem--;
                rbegin(type[i])[j] = 1;
            } else rbegin(type[i])[j] = -1;
        }
        debug(i,  type[i]);
    }

    ll sum = 0;
    vector ans(n, vector<int>(m, -1));
    int round_low = 0;
    for (int i = 0; i < n; i++) {
        debug(i, ans[i]);
        for (int j = 0; j < m; j++) {
            if (type[i][j] == -1) {
                sum -= x[i][j];
                ans[i][j] = round_low++;
                if (round_low >= k) round_low -= k;
            }
        }
        int round = round_low;
        for (int j = 0; j < m; j++) {
            if (type[i][j] == 1) {
                sum += x[i][j];
                ans[i][j] = round++;
                if (round >= k) round -= k;
            }
        }
        debug(i, ans[i]);
    }
    allocate_tickets(ans);
    return sum;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:57:9: note: in expansion of macro 'debug'
   57 |         debug(i, score[i]);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:74:5: note: in expansion of macro 'debug'
   74 |     debug(c1, use);
      |     ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:78:9: note: in expansion of macro 'debug'
   78 |         debug(c1, i, use);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:83:9: note: in expansion of macro 'debug'
   83 |         debug(c1, i, use);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:102:9: note: in expansion of macro 'debug'
  102 |         debug(i, type[i]);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:120:9: note: in expansion of macro 'debug'
  120 |         debug(i,  type[i]);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:127:9: note: in expansion of macro 'debug'
  127 |         debug(i, ans[i]);
      |         ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
   10 | #define debug(args...) {42;}
      |                         ^~
tickets.cpp:143:9: note: in expansion of macro 'debug'
  143 |         debug(i, ans[i]);
      |         ^~~~~

• Subtask 1: 0 / 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