Submission #1197832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197832		The_Samurai	Olympiads (BOI19_olympiads)	C++20	100 / 100	16 ms	3660 KiB

olympiads

// I stand with PALESTINE



//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

// #define int long long
#define ff first
#define ss second
#define sz(a) (int) (a).size()
//template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;

namespace io {

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; }

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const map<F, S> &mp) {
        for (auto it: mp) { os << it << endl; }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const vector<F> &v) {
        bool space = false;
        for (F x: v) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const deque<F> &d) {
        bool space = false;
        for (F x: d) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const set<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const multiset<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x << x;
        }
        return os;
    }

    template<typename F, typename S>
    istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; }

    template<typename F>
    istream &operator>>(istream &is, vector<F> &v) {
        for (F &x: v) { is >> x; }
        return is;
    }

    long long fastread() {
        char c;
        long long d = 1, x = 0;
        do c = getchar(); while (c == ' ' || c == '\n');
        if (c == '-') c = getchar(), d = -1;
        while (isdigit(c)) {
            x = x * 10 + c - '0';
            c = getchar();
        }
        return d * x;
    }

    static bool sep = false;

    using std::to_string;

    string to_string(bool x) {
        return (x ? "true" : "false");
    }

    string to_string(const string &s) { return "\"" + s + "\""; }

    string to_string(const char *s) { return "\"" + string(s) + "\""; }

    string to_string(const char &c) {
        string s;
        s += c;
        return "\'" + s + "\'";
    }

    template<typename Type>
    string to_string(vector<Type>);

    template<typename F, typename S>
    string to_string(pair<F, S>);

    template<typename Collection>
    string to_string(Collection);

    template<typename F, typename S>
    string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; }

    template<typename Type>
    string to_string(vector<Type> v) {
        bool sep = false;
        string s = "[";
        for (Type x: v) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "]";
        return s;
    }

    template<typename Collection>
    string to_string(Collection collection) {
        bool sep = false;
        string s = "{";
        for (auto x: collection) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "}";
        return s;
    }

    void print() {
        cout << endl;
        sep = false;
    }

    template<typename F, typename... Other>
    void print(F ff, Other... other) {
        if (sep) cout << " | ";
        sep = true;
        cout << to_string(ff);
        print(other...);
    }

}
using namespace io;

namespace utils {

    template<typename F, typename S>
    inline void maxs(F &a, S b) { a = a > b ? a : b; }

    template<typename F, typename S>
    inline void mins(F &a, S b) { a = a < b ? a : b; }

    template<typename F, typename S>
    long long max(F a, S b) { return a > b ? a : b; }

    template<typename F, typename S>
    long long min(F a, S b) { return a < b ? a : b; }

    constexpr long long operator "" _E(unsigned long long n) {
        long long p = 1, a = 10;
        for (int i = 0; i < n; i++) p *= a;
        return p;
    }

    random_device rd;
    mt19937 mt(rd());

    template<typename T>
    T rand(T l, T r) {
        uniform_int_distribution<T> dist(l, r);
        return dist(mt);
    };

}
using namespace utils;


#ifdef sunnatov
#define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ );
#else
#define print( ... ) 42
#endif

const int mod = 9_E + 7;
const double EPS = 1e-7;
long long doxuya = 18_E + 10;
int INF = 9_E + 10;
const char nl = '\n';

int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

/*

*/

using ll = long long;

ll get_id(const vector<int> &v) {
    ll id = 0;
    for (int x: v) id = id * 501 + x;
    return id;
}

void solution(istream &cin, ostream &cout, const int &test_case) {
    int n = 6, k = 2, count = 7;
    cin >> n >> k >> count;
    vector a(n, vector(k, 1));
    for (auto &v: a) for (int &x: v) x = rand(1, 10);
    cin >> a;
    print(n, k, count);
    print(a);

    auto brute = [&]() -> int {
        vector<int> all;
        for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
            int val = max(a[i][0], a[j][0]) + max(a[i][1], a[j][1]);
            all.emplace_back(val);
        }
        sort(all.rbegin(), all.rend());
        return all[count - 1];
    };

    vector vec(k, vector(n, make_pair(0, 0)));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            vec[i][j] = make_pair(a[j][i], j);
        }
    }
    for (int i = 0; i < k; i++) {
        sort(vec[i].rbegin(), vec[i].rend());
        print(vec[i]);
    }
    
    int sum = 0;
    for (int i = 0; i < k; i++) sum += vec[i][0].ff;
    set<tuple<int, vector<int>, bool>, greater<>> st;
    st.emplace(sum, vector(k, 0), false);

    set<ll> vis, vis2;
    vis2.insert(get_id(vector(k, 0)));
    auto add = [&](vector<int> ind) -> bool {
        sort(ind.begin(), ind.end());
        vis.insert(get_id(ind));
        if (sz(vis) == count) {
            print(ind);
            int val = 0;
            for (int i = 0; i < k; i++) {
                int mx = 0;
                for (int j = 0; j < k; j++) maxs(mx, a[ind[j]][i]);
                val += mx;
            }
            // print(brute());
            // print(val);
            // assert(val == brute());
            cout << val;
            return true;
        }
        return false;
    };

    const int N = 1.8e6;

    while (!st.empty()) {
        auto [shit, org, bad] = *st.begin(); st.erase(st.begin());
        if (!bad) {

            vector<int> ind(k);
            set<int> diff;
            vector<bool> exist(n);
            for (int i = 0; i < k; i++) diff.insert(vec[i][org[i]].ss);
            int z = 0;
            for (int i: diff) ind[z++] = i, exist[i] = true;
            // print(shit, org);
            // print(diff);
            // print(sz(vis), sz(vis2));
            
            if (sz(diff) == k) {
                if (add(ind)) return;
            } else if (sz(diff) + 1 == k) {
                for (int i1 = 0; i1 < n; i1++) {
                    if (exist[i1]) continue;
                    ind[k - 1] = i1;
                    if (add(ind)) return;
                }
            } else if (sz(diff) + 2 == k) {
                for (int i1 = 0; i1 < n; i1++) {
                    if (exist[i1]) continue;
                    ind[k - 1] = i1;
                    for (int i2 = i1 + 1; i2 < n; i2++) {
                        if (exist[i2]) continue;
                        ind[k - 2] = i2;
                        if (add(ind)) return;
                    }
                }
            } else if (sz(diff) + 3 == k) {
                for (int i1 = 0; i1 < n; i1++) {
                    if (exist[i1]) continue;
                    ind[k - 1] = i1;
                    for (int i2 = i1 + 1; i2 < n; i2++) {
                        if (exist[i2]) continue;
                        ind[k - 2] = i2;
                        for (int i3 = i2 + 1; i3 < n; i3++) {
                            if (exist[i3]) continue;
                            ind[k - 3] = i3;
                            if (add(ind)) return;
                        }
                    }
                }
            } else if (sz(diff) + 4 == k) {
                for (int i1 = 0; i1 < n; i1++) {
                    if (exist[i1]) continue;
                    ind[k - 1] = i1;
                    for (int i2 = i1 + 1; i2 < n; i2++) {
                        if (exist[i2]) continue;
                        ind[k - 2] = i2;
                        for (int i3 = i2 + 1; i3 < n; i3++) {
                            if (exist[i3]) continue;
                            ind[k - 3] = i3;
                            for (int i4 = i3 + 1; i4 < n; i4++) {
                                if (exist[i4]) continue;
                                ind[k - 4] = i4;
                                if (add(ind)) return;
                            }
                        }
                    }
                }
            } else {
                for (int i1 = 0; i1 < n; i1++) {
                    if (exist[i1]) continue;
                    ind[k - 1] = i1;
                    for (int i2 = i1 + 1; i2 < n; i2++) {
                        if (exist[i2]) continue;
                        ind[k - 2] = i2;
                        for (int i3 = i2 + 1; i3 < n; i3++) {
                            if (exist[i3]) continue;
                            ind[k - 3] = i3;
                            for (int i4 = i3 + 1; i4 < n; i4++) {
                                if (exist[i4]) continue;
                                ind[k - 4] = i4;
                                for (int i5 = i4 + 1; i5 < n; i5++) {
                                    if (exist[i5]) continue;
                                    ind[k - 5] = i5;
                                    if (add(ind)) return;
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < k and sz(vis2) < N; i++) {
            org[i]++;
            if (org[i] < n) {
                ll id = get_id(org);
                if (sz(vis2) > N or vis2.count(id)) {
                    org[i]--;
                    continue;
                }
                int now = 0;
                bool bad = false;
                for (int j = 0; j < k; j++) {
                    int mx = 0;
                    // for (int l = 0; l < k; l++) maxs(mx, a[vec[l][org[l]].ss][j]);
                    mx = vec[j][org[j]].ff;
                    if (mx != vec[j][org[j]].ff) bad = true;
                    now += mx;
                }
                // print(now, org);
                vis2.insert(id);
                st.emplace(now, org, bad);
            }
            org[i]--;
        }
    }
    // print(sz(vis));
    // while (true);
    // assert(false);
}

int32_t main() {
    clock_t startTime = clock();
    cin.tie(0)->sync_with_stdio(false);
    srand(time(0));

    std::istream &in(std::cin);
    std::ostream &out(std::cout);

    int32_t queries = 1;

#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    // cin >> queries;
#endif

    for (int32_t test_case = 1; test_case <= queries; test_case++) {
        print(test_case);
        solution(cin, cout, test_case);
        cout << nl;
    }

#ifdef sunnatov
    cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return EXIT_SUCCESS;
}

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