Submission #709439

#	Time	Username	Problem	Language	Result	Execution time	Memory
709439		lukameladze	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1359 ms	240644 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair <ll, ll>
#define piii pair <ll, pii>
#define pb push_back
using namespace std;
const int N = 2005;
ll ans, sign[N][N];
set <ll> neg[N],pos[N];
vector < piii > v;
bool cmp(int a, int b) {
    return neg[a].size() > neg[b].size();
}
long long find_maximum(int k, vector< vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	vector< vector <int> > answ;
	answ = vector < vector <int> > (n, vector <int> (m, -1));
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < k; j++) {
	        ans -= x[i][j];
	        sign[i][j] = -1; // neg
	        v.pb({x[i][j] + x[i][m - (k - j)], {i, j}});
        }
    }
    sort(v.rbegin(),v.rend());
    for (int i = 0; i < (k * n) / 2; i++) {
        int xi = v[i].s.f; int xj = v[i].s.s;
        ans += v[i].f; sign[xi][xj] = 0; sign[xi][m - (k - xj)] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (sign[i][j] == -1) {
                neg[i].insert(j);
            } else if (sign[i][j] == 1) pos[i].insert(j);
        }
    }
    vector <int> id;
    for (int i = 0; i < n; i++) {
        id.pb(i);
    }
    for (int i = 1; i <= k; i++) {
        sort(id.begin(), id.end(), cmp);
        int cnt = 0;
        for (int idx : id) {
            cnt++;
            if (cnt <= n / 2) {
                answ[idx][*neg[idx].begin()] = i - 1;
                neg[idx].erase(neg[idx].begin());
            } else {
                answ[idx][*pos[idx].begin()] = i - 1;
                pos[idx].erase(pos[idx].begin());
            }
        }
    }
	allocate_tickets(answ);
	return ans;
}

• 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