Submission #947137

#	Time	Username	Problem	Language	Result	Execution time	Memory
947137		Pring	Olympiads (BOI19_olympiads)	C++17	0 / 100	2053 ms	262144 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 6> A;

const int MXN = 505;
int n, k, m;
A abt[MXN];
A scr[MXN], rnk[MXN];
pii dist[MXN];

int get_val(A r) {
    int ans = 0;
    FOR(dim, 0, k) ans += abt[scr[r[dim]][dim]][dim];
    return ans;
}

class CMP {
public:
    bool operator()(A a, A b) {
        return get_val(a) < get_val(b);
    }
};

priority_queue<A, vector<A>, CMP> pq;
set<vector<int>> S;

void DIST(int dim) {
    FOR(i, 0, n) dist[i] = mp(abt[i][dim], i);
    sort(dist, dist + n, greater<pii>());
    FOR(i, 0, n) {
        scr[i][dim] = dist[i].sc;
        rnk[dist[i].sc][dim] = i;
    }
}

void PRE() {
    FOR(dim, 0, k) DIST(dim);
}

int P(int n, int k) {
    int ans = 1;
    FOR(i, n - k + 1, n + 1) ans *= i;
    FOR(i, 1, k + 1) ans /= i;
    return ans;
}

int bruh(A id) {
    auto check = [&](int i) -> bool {
        FOR(dim, 0, k) {
            if (id[dim] == i) return 0;
            if (rnk[i][dim] < rnk[id[dim]][dim]) return 0;
        }
        return 1;
    };
    int ans = 0;
    FOR(i, 0, n) ans += check(i);
    return ans;
}

int cnt(A r) {
    A id;
    FOR(dim, 0, k) id[dim] = scr[r[dim]][dim];
    // FOR(dim, 0, k) cout << id[dim] << " \n"[dim == k - 1];
    FOR(dim, 0, k) {
        FOR(dim2, 0, k) {
            if (dim == dim2) continue;
            if (rnk[id[dim]][dim2] < rnk[id[dim2]][dim2]) return 0;
        }
    }
    int cnt;
    {
        set<int> S;
        FOR(dim, 0, k) S.insert(id[dim]);
        cnt = S.size();
    }
    {
        vector<int> v;
        FOR(dim, 0, k) v.push_back(id[dim]);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        if (!S.insert(v).sc) return 0;
    }
    return P(bruh(id), k - cnt);
}

int SOLVE() {
    {
        A sr;
        FOR(dim, 0, k) sr[dim] = 0;
        pq.push(sr);
    }
    int X = 0;
    while (pq.size()) {
        A now = pq.top();
        pq.pop();
        if (++X % 1000 == 0) cout << X << endl;
        // debug(cnt(now));
        if ((m -= cnt(now)) <= 0) return get_val(now);
        FOR(dim, 0, k) {
            if (++now[dim] == n) {
                now[dim]--;
                continue;
            }
            pq.push(now);
            now[dim]--;
        }
    }
    return 0;
}

void miku() {
    cin >> n >> k >> m;
    FOR(i, 0, n) {
        FOR(dim, 0, k) cin >> abt[i][dim];
    }
    PRE();
    cout << SOLVE() << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32