Submission #552329

#	Time	Username	Problem	Language	Result	Execution time	Memory
552329		hoanghq2004	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	760 ms	84056 KiB

tickets

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "tickets.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());

//static int n;
//static int m;
//static int k;
//static std::vector<std::vector<int>> d;
//static std::vector<std::vector<int>> x;
//static int called = 0;
//
//static void check(bool cond, std::string message) {
//    if (!cond) {
//        printf("%s\n", message.c_str());
//        exit(0);
//    }
//}
//
//
//void allocate_tickets( std::vector<std::vector<int>> _d) {
//    check(!called, "allocate_tickets called more than once");
//    d = _d;
//    check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
//    for (int i = 0; i < n; i++) {
//        check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
//    }
//    called = 1;
//}

long long find_maximum(int k, vector <vector <int> > x) {
	int n = x.size();
	int m = x[0].size();
	vector <vector <int> > ans(n);
	vector <pair <int, int> > tmp;
	long long B = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < k; ++j) {
            B -= x[i][j];
            tmp.push_back({x[i][j] + x[i][m - k + j], i});
		}
//    cout << B << '\n';
    sort(tmp.begin(), tmp.end(), greater<>());
    vector <int> used(n, 0);
    int cnt = 0;
    for (auto [x, i]: tmp) {
        if (cnt == n * k / 2) break;
        ++used[i];
        ++cnt;
        B += x;
    }
//    cout << B << endl;
    vector <int> c1(n, 0), c2(n, 0);
    for (int i = 0, cur = 0; i < n; ++i) {
        ans[i].assign(m, -1);
        for (int j = m - used[i]; j < m; ++j) {
            ans[i][j] = cur;
            cur = (cur + 1) % k;
        }
        for (int j = 0; j < k - used[i]; ++j) ans[i][j] = (j + cur) % k;
    }
	allocate_tickets(ans);
	return B;
}
//
//
//int main() {
//    assert(scanf("%d %d %d", &n, &m, &k) == 3);
//    x.resize(n);
//    for (int i = 0; i < n; i++) {
//        x[i].resize(m);
//        for (int j=0; j < m; j++) {
//            assert(scanf("%d", &x[i][j]) == 1);
//        }
//    }
//    fclose(stdin);
//    long long answer = find_maximum(k, x);
////    assert(0);
//    check(called, "failure to call allocate_tickets");
//    printf("%lld\n", answer);
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            if (j) printf(" ");
//            printf("%d", d[i][j]);
//        }
//        printf("\n");
//    }
//    fclose(stdout);
//    return 0;
//}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [x, i]: tmp) {
      |               ^

• 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