Submission #1308968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308968		rohit_flytsapp	Izbori (COCI17_izbori)	C++20	80 / 80	15 ms	444 KiB

izbori

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int find(vector<int> &arr, int x){
    for(int i=0; i<arr.size(); i++) if(arr[i] == x) return i;
    return -1;
}

bool get_bit(int x, int p){
    if((x & (1<<p)) == 0) return false;
    return true;
}

void fill_bits(vector<bool> &vec, int bits){
    for(int i=0; i<vec.size(); i++){
        vec[i] = (bits & 1);
        bits>>=1;
    }
}

int count_ones(vector<bool>& vec){
    int ret = 0;
    for(auto el: vec) if(el) ret++;
    return ret;
}

int main(){
    
    int n, m, k;
    cin>>n>>m>>k; k--;
    vector<vector<int>> pres(n, vector<int>(m));

    for(auto &vec: pres){
        for(auto &el: vec) {
            cin>>el; el--;
        };
    }


    vector<int> votes(m, 0);
    for(int i=0; i<n; i++){
        votes[pres[i][0]] ++;
    }
    int mx = 0, mxo = 0;
    for(int c=0; c<m; c++){
        if(mx < votes[c]){
            mx = votes[c];
            mxo = c;
        }
    }
    cout<<mxo+1<<"\n";

    int answer = 1e8;

    for(int resents= 0; resents < (1<<m); resents++){
        if(get_bit(resents, k)) continue;

        vector<bool> rv(m, false);
        fill_bits(rv, resents);

        vector<int> votes(m);
        for(int i=0; i<n; i++){
            int c = pres[i][0];
            for(int j=1; rv[c]; j++){
                c = pres[i][j];
            }
            votes[c]++;
        }
        int mx = 0, mxo = 0;
        for(int c=0; c<m; c++){
            if(mx < votes[c]){
                mx = votes[c];
                mxo = c;
            }
        }
        if(mxo == k){
            answer = min(answer, count_ones(rv));
        }

    }
    cout<<answer<<"\n";

    return 0;
}

• Subtask 1: 80 / 80