제출 #303388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303388		Kevin_Zhang_TW	카니발 티켓 (IOI20_tickets)	C++17	11 / 100	2 ms	896 KiB

tickets

#include "tickets.h"
#include <vector>

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 300010;
vector<vector<int>> x, answer, so;
int k, n, m;
void init() {
    so.resize(n, vector<int>(m));
    int r = 0;
    for (auto &i : so) {
        iota(begin(i), end(i), 0);
        sort(begin(i), end(i), [&](int a, int b) {
            return x[r][a] < x[r][b];
        });
        ++r;
    }
    answer.resize(n, vector<int>(m, -1));
}

ll calall() {
    ll res = 0;
    vector<vector<int>> val(k);
    for (int i = 0;i < n;++i)
        for (int j = 0;j < m;++j) 
            if (answer[i][j] != -1)
                val[ answer[i][j] ].pb( x[i][j] );
    for (auto &V : val) {
        sort(begin(V), end(V));
        int m = V[n/2];
        for (int u : V)
            res += abs(m - u);
    }
    return res;
}
void nobuild() {
	for (int i = 0; i < n; i++) {
        auto &row = answer[i];
		for (int j = 0; j < m; j++) 
			if (j < k) 
				row[j] = j;
			else
				row[j] = -1;
	}
}
int mxmx() { int res = 0; for (auto &V : x) res = max(res, *max_element(begin(V), end(V))); return res; }
void build01() {
    vector<int> c0(m), id(m);
    for (int i = 0;i < n;++i) {
        c0[i] = count(begin(x[i]), end(x[i]), 0);
        id[i] = i;
    }
    sort(begin(id), end(id), [&](int a, int b) {
        return c0[a] > c0[b];
    });
    for (int i = 0;i < n;++i) {
        int r = id[i];
        if (i >= n/2)
            reverse(begin(so[r]), end(so[r]));
        for (int j = 0;j < k;++j)
            answer[r][ so[i][j] ] = j;
    }
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	n = x.size();
	m = x[0].size();
    ::k = k;
    ::x = x;
    init();
    if (m == 1) nobuild();
    else if (mxmx() <= 1) build01();
	allocate_tickets(answer);
	return calall();
}

• 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