Submission #1190064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190064		crafticat	Olympiads (BOI19_olympiads)	C++20	44 / 100	814 ms	327680 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define R0F(i, n) for (int i = n - 1; i >= 0;i--)
#define FOR(i, j, n) for(int i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;

constexpr int INF = 1e9;

V<vi> v;
int n, k, c;

int eval(vi a) {
    vi opt(k);
    for (auto i : a) {
        F0R(j, k) {
            opt[j] = max(opt[j], v[i][j]);
        }
    }

    return accumulate(opt.begin(), opt.end(), 0, [](int x, int y) {
        return x + y;
    });
}

bool cmp(pair<int, vi> x, pair<int, vi> y) {
    return !(x < y);
}

vi imp;

V<vi> near(vi x) {
    V<vi> ans;

    F0R(i, k) {
        vi copy = x;
        for (auto j : imp) {
            copy[i] = j;
            bool valid = 1;
            for (auto v : x) {
                if (v == j) valid = false;
            }

            if (valid) ans.push_back(copy);
        }
    }

    return ans;
}


long long MOD = 1e9 + 7;
int MAX = 1e6 * 6 + 1;

long long hashMy(vi x) {
    long long ans = 0, mul = 1;
    for (auto v : x) {
        ans += v * mul;
        mul *= 1e6;
        ans %= MOD;
        mul %= MOD;
    }
    return ans;
}

#ifndef DEBUG
int main() {
    cin >> n >> k >> c;

    v.resize(n, vi(k));
    F0R(i, n) {
        F0R(j, k)
            cin >> v[i][j];
    }

    V<set<pair<int,int>>> opts(k);
    F0R(i, k) {
        F0R(j, n) {
            opts[i].insert({v[j][i], j});
        }
    }

    vi opt(k);
    F0R(i, k) {
        opt[i] = opts[i].rbegin()->second;

        int iter = 0;
        for (auto rit = opts[i].rbegin(); rit != opts[i].rend(); rit++)
            imp.push_back(rit->second);
    }

    sort(imp.begin(), imp.end());
    imp.erase( unique( imp.begin(), imp.end() ), imp.end() );


    sort(opt.begin(), opt.end());
    opt.erase( unique( opt.begin(), opt.end() ), opt.end() );

    while (opt.size() < k) {
        F0R(i, n) {
            bool valid = true;
            for (auto x : opt)
                if (x == i) valid = false;

            if (valid) {
                opt.push_back(i);
                break;
            }
        }
    }

    unordered_map<long long, bool> vis;
    V<V<vi>> pq(MAX);

    pq[eval(opt)].push_back(opt);

    int last = 0;

    R0F(val, MAX) {
        while (!pq[val].empty() and c > 0) {
            auto vec = pq[val].back(); pq[val].pop_back();

            sort(vec.begin(), vec.end());
            long long h = hashMy(vec);
            if (vis[h]) continue;
            c--;
            last = val;
            vis[h] = 1;

            for (auto y : near(vec)) {
                sort(y.begin(), y.end());

                long long h2 = hashMy(y);

                if (vis[h2]) continue;
                pq[eval(y)].push_back(y);
            }
        }
    }

    cout << last << endl;
}

#endif

#if DEBUG

int rand(int a, int b) {
    return a + rand() % (b -a  +1);
}

int main() {
    n = 500, k = 6, c = 2000;

    v.resize(n, vi(k));
    int lastT = clock();
    F0R(i, n) {
        F0R(j, k)
            v[i][j] = rand(1, 1e6);
    }

    V<set<pair<int,int>>> opts(k);
    F0R(i, k) {
        F0R(j, n) {
            opts[i].insert({v[j][i], j});
        }
    }

    vi opt(k);
    F0R(i, k) {
        opt[i] = opts[i].rbegin()->second;

        int iter = 0;
        for (auto rit = opts[i].rbegin(); rit != opts[i].rend(); rit++)
            imp.push_back(rit->second);
    }

    sort(imp.begin(), imp.end());
    imp.erase( unique( imp.begin(), imp.end() ), imp.end() );


    sort(opt.begin(), opt.end());
    opt.erase( unique( opt.begin(), opt.end() ), opt.end() );

    while (opt.size() < k) {
        F0R(i, n) {
            bool valid = true;
            for (auto x : opt)
                if (x == i) valid = false;

            if (valid) {
                opt.push_back(i);
                break;
            }
        }
    }

    unordered_map<long long, bool> vis;
    V<vi> buckets(1e6);

    pq.emplace(eval(opt), opt);
    int last = 0;

    while (!pq.empty() and c > 0) {
        auto [val, vec] = *pq.begin(); pq.erase(pq.begin());
        while (pq.size() > c) pq.erase(prev(pq.end()));

        sort(vec.begin(), vec.end());
        long long h = hashMy(vec);

        if (vis[h]) continue;
        last = val;
        vis[h] = 1;
        c--;

        for (auto y : near(vec)) {
            sort(y.begin(), y.end());

            long long h2 = hashMy(y);

            if (vis[h2]) continue;
            pq.emplace(eval(y),y);
        }
    }

    cout << last << endl;
    cout << clock() - lastT << endl;
}
#endif

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