Submission #303471

#	Time	Username	Problem	Language	Result	Execution time	Memory
303471		Kevin_Zhang_TW	카니발 티켓 (IOI20_tickets)	C++17	41 / 100	833 ms	74476 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<ll>> 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));
        ll m = V[n/2];
        for (ll 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() ]; }
ll getcal(vector<int> v) {
    sort(begin(v), end(v));
    ll res = 0, m = v[n/2];
    for (int u : v) res += abs(m-u);
    return res;
}
int get(int i) { 
    return x[i][so[i][0]] + x[i][so[i].back()];
}
void take(int i, bool lft, int day) {
    int id = lft ? so[i][0] : so[i].back();
    answer[i][id] = day;
    if (lft) 
        so[i].pop_front();
    else
        so[i].pop_back();
}

void pick(int day) {
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    sort(a.begin(), a.end(), [&](int x, int y) {
            return get(x) < get(y);
        });
    for (int i = 0;i < n;++i) 
        take(a[i], i<n/2, day);

//    sort(begin(a), end(a), [&](auto a, auto b) {
//        return a() < b();
//    });
//    DE(day, '\n');
//
//    vector<int> p1, p2;
//    vector<PTR> pl1, pl2;
//    auto tst = [&](vector<int> &p, vector<PTR> &pl) {
//        int cnt = 0;
//        vector<bool> vis(n), skip(n);
//        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;
//            pl.pb(i);
//            ++cnt;
//        }
//        assert(cnt == n);
//    };
//    tst(p1, pl1);
//    reverse(begin(a), end(a));
//    tst(p2, pl2);
////    if (min(getcal(p1), getcal(p2)) == 2307346107)
////        assert(max(getcal(p2), getcal(p1)) == 2727881086);
//    if (getcal(p2) > getcal(p1))
//        swap(pl1, pl2);
//    for (auto i : pl1) {
//        i.set(day);
//        int row = i.first;
//        if (SM(row) == i())
//            so[row].pop_front();
//        else
//            so[row].pop_back();
//    }
}
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);
    ll v = calall();
	return v;
}

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: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10