Submission #303434

#	Time	Username	Problem	Language	Result	Execution time	Memory
303434		Kevin_Zhang_TW	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	821 ms	72188 KiB

tickets

#include "tickets.h"
#include <vector>
#define KEV
#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
vector<vector<int>> x, answer;
vector<deque<int>> so;
int k, n, m;
void init() {
    so.resize(n, deque<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(n), id(n);
    for (int i = 0;i < n;++i) {
        c0[i] = count(begin(x[i]), end(x[i]), 0);
        id[i] = i;
    }
    for (int d = 0;d < k;++d) {
        sort(begin(id), end(id), [&](int a, int b) {
            return c0[a] > c0[b];
        });
        for (int i = 0;i < n;++i) {
            int row = id[i];
            if (i < n/2) {
                answer[row][ so[row][0] ] = d;
                c0[ row ] -= x[row][so[row][0]] == 0;
                so[row].pop_front();
            }
            else {
                answer[row][ so[row].back() ] = d;
                c0[ row ] -= x[row][so[row].back()] == 0;
                so[row].pop_back();
            }
        }
    }
}
struct PTR : pair<int,int> {
    PTR(int x, int y) { first = x, second = y; }
    int& operator()() { return x[first][second]; }
    void set(int day) { answer[first][second] = day; }
};
int SM(int row) { return x[row][ so[row][0] ]; }
int BG(int row) { return x[row][ so[row].back() ]; }
void pick(int day) {
    if (so[0].size() == 1) {
        for (int i = 0;i < n;++i)
            answer[i][ so[i][0] ] = day;
        return;
    }
    vector<PTR> a;
    for (int i = 0;i < n;++i) {
        a.pb(i, so[i][0]);
        a.pb(i, so[i].back());
    }
    sort(begin(a), end(a), [&](auto a, auto b) {
            return a() < b();
            });
    vector<bool> vis(n), skip(n);
    DE(day, '\n');
    for (int i = 0;i < n;++i)
        assert(so[i].size() > 1);
    int cnt = 0;
    for (auto i : a) {
        int row = i.first;
        if (vis[row]) continue;
        if (cnt >= n/2 && !skip[row]) {
            skip[row] = true;
            continue;
        }
        vis[row] = true;
        i.set(day);
        if (i() == SM(row))
            so[ row ].pop_front();
        else
            so[ row ].pop_back();
        ++cnt;
    }
    assert(cnt == n);
}
void solve() {
    for (int d = 0;d < k;++d)
        pick(d);
}
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();
    else solve();
	allocate_tickets(answer);
	return calall();
}

Compilation message (stderr)

tickets.cpp:10:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   10 | void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
      |            ^~~~
tickets.cpp:10:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   10 | void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
      |                    ^~~~

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