Submission #123008

#	Time	Username	Problem	Language	Result	Execution time	Memory
123008		model_code	Olympiads (BOI19_olympiads)	C++14	0 / 100	140 ms	16588 KiB

olympiads

//Author: Oliver-Matis Lill
//Around O(C N log(C)), A* search of solutions
#include<iostream>
#include<bitset>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
using namespace std;

vector<int> pairwise_min(vector<int> a, vector<int> b) {
    vector<int> result(a.size());
    for(int i=0; i<(int)a.size(); i++) {
        result[i] = min(a[i], b[i]);
    }
    return result;
}

vector<int> pairwise_max(vector<int> a, vector<int> b) {
    vector<int> result(a.size());
    for(int i=0; i<(int)a.size(); i++) {
        result[i] = max(a[i], b[i]);
    }
    return result;
}

int sum(vector<int> a) {
    return accumulate(a.begin(), a.end(), 0);
}

struct Solution_State {
    int expected;
    vector<int> taken;
    bitset<500> excluded;
    
    bool operator<(Solution_State r) const {
        return expected < r.expected;
    }
};

int combs(int n, int k) {
    int result = 1;
    for(int i=n; i>n-k; i--) {
        result *= i;
    }
    for(int i=1; i<=k; i++ ) {
        result /= i;
    }
    return result;
}

int main() {
    int n, k, c;
    cin >> n >> k >> c;
    c--;
    
    vector<vector<int> > scores(n, vector<int>(k));
    for(int i=0; i<n; i++) {
        for(int j=0; j<k; j++) {
            cin >> scores[i][j];
        }
    }
    
    vector<vector<pair<int, int> > > order(k);
    // vector<vector<vector<int> > > max_left(k, vector<vector<int> >(n, vector<int>(k, 0)));
    
    for(int j=0; j<k; j++) {
        for(int i=0; i<n; i++) {
            order[j].push_back({scores[i][j], i});
        }
        sort(order[j].rbegin(), order[j].rend());
        
        /*
        bitset<500> excluded;
        for(int i=0; i<n; i++) {
            for(int o=0; i<n; o++) {
                if(!excluded[o]) {
                    max_left[j][i] = pairwise_max(min_left[j][i], scores[o]);
                }
            }
            excluded[i] = true;
        }
        */
    }
    
    vector<int> solutions;
    priority_queue<Solution_State> heap;
    {
        vector<int> max_per_event(k, 0);
        for(int i=0; i<n; i++) {
            max_per_event = pairwise_max(max_per_event, scores[i]);
        }
        heap.push(Solution_State({sum(max_per_event), {}, bitset<500>()}));
    }
    
    while((int)solutions.size() <= c+10 && heap.size() > 0) {
        Solution_State sol = heap.top();
        heap.pop();
        
        if((int)sol.taken.size() == k) {
            int left = k;
            for(int j=0; j<k; j++) {
                int index_taken = order[j][sol.taken[j]].second;
                left -= !sol.excluded[index_taken];
                sol.excluded[index_taken] = 1;
            }
            for(int i=0; i<combs(n-sol.excluded.count(), left) && (int)solutions.size() <= c+10; i++) {
                solutions.push_back(sol.expected);
            }
            continue;
        }
        
        int j = sol.taken.size();
        int overshot = 0;
        vector<int> max_per_event(k, 0);
        bitset<500> cur_excluded;
        for(int i=0; i<n; i++) cur_excluded[i] = 1;
        
        for(int i=n-1; i>=0; i--) {
            if(!sol.excluded[order[j][i].second]) {
                cur_excluded[order[j][i].second] = 0;
                for(int o=0; o<j; o++) {
                    if(order[o][sol.taken[o]].second == order[j][i].second) {
                        overshot++;
                    }
                }
                max_per_event = pairwise_max(max_per_event, scores[order[j][i].second]);
                
                if(overshot == j) {
                    vector<int> new_taken = sol.taken;
                    new_taken.push_back(i);
                    heap.push(Solution_State({sum(max_per_event), new_taken, cur_excluded}));
                }
            }
        }
    }
    
    for(int i=max(0, c-9); i<c; i++) {
        cerr << solutions[i] << ' ';
    }
    cerr << "| " << solutions[c] << " | ";
    for(int i=c+1; i<c+10 && i < (int)solutions.size(); i++) {
        cerr << solutions[i] << ' ';
    }
    cerr << '\n';
    for(int i=0;i+1 < (int)solutions.size(); i++) {
        if(solutions[i] < solutions[i+1]) {
            cerr << "Invalid ordering\n";
            throw 1;
        }
    }
    {
        vector<int> uniques = solutions;
        uniques.erase(uniques.begin() + c + 1, uniques.end());
        uniques.resize(unique(uniques.begin(), uniques.end()) - uniques.begin() );
        cerr << uniques.size() << " unique values\n";
    }
    
    cout << solutions[c] << '\n';
    
    return 0;
}

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