Submission #857067

#	Time	Username	Problem	Language	Result	Execution time	Memory
857067		rog1gor	Let's Win the Election (JOI22_ho_t3)	C++14	5 / 100	3 ms	348 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using city_struct = pair<pair<int32_t, int32_t>, int32_t>;
using vote_struct = pair<int32_t, int32_t>;

//? usefull const values
#define PRECISION 100000
#define NO_DELEGATE 14369

//? vector aliases
#define city_info first
#define get_delegate first
#define get_vote second

#define vote first

#define index second

//? Return time needed to debate for time_needed having
//? acquired_delegates number of delegates  
uint64_t time_to_acquire(int32_t time_needed, int32_t acquired_delegates) {
    uint64_t time_spent = 0;

    //? Integer part of number
    time_spent += (time_needed / acquired_delegates) * PRECISION;
    
    //? Fractional part of number
    uint64_t additional_time =
        PRECISION * (time_needed % acquired_delegates);
    additional_time /= acquired_delegates;
    time_spent += additional_time;

    return time_spent;
}

uint64_t acquire_d_delegates(size_t d, int32_t votes_to_acquire,
        const vector<city_struct>& Cities,
        const vector<vote_struct>& Votes) {
    int32_t acquired_delegates = 1;  //? Let's say that we are a delegate as well
    uint64_t time_spent = 0;

    vector<bool> did_city_vote;
    did_city_vote.resize(Cities.size());

    //? Acquire d delegates
    for (size_t i = 0; i < d; i++) {
        //? Acquire voite and delegate
        time_spent += 
            time_to_acquire(Cities[i].city_info.get_delegate, acquired_delegates);

        //? Delegate and a vote is acquired
        votes_to_acquire--;
        acquired_delegates++;

        //? Mark that this city voted
        did_city_vote[Cities[i].index] = true;
    }

    //? Acquire rest of the votes
    for (auto city_vote : Votes) {
        if (votes_to_acquire == 0) break;
        if (did_city_vote[city_vote.index]) continue;

        //? Acquire vote
        time_spent += time_to_acquire(city_vote.vote, acquired_delegates);
        did_city_vote[city_vote.index] = true;

        //? Vote is acquired
        votes_to_acquire--;
    }

    return time_spent;
}

int main() {
    //? Read
    int32_t N, K; cin >> N >> K;
    
    //? Vector with all cities information
    vector<city_struct> Cities;
    Cities.resize(N);
    //? Vector with only information about votes
    vector<vote_struct> Votes;
    Votes.resize(N);

    int32_t DELEGATE_NUM = N;
    //? Read city information
    for (int32_t i = 0; i < N; i++) {
        cin >> Cities[i].city_info.get_vote >> Cities[i].city_info.get_delegate;
        Cities[i].index = i;

        //? If there is no delegate we are setting the time to a special value
        if (Cities[i].city_info.get_delegate == -1) {
            Cities[i].city_info.get_delegate = NO_DELEGATE;
            DELEGATE_NUM--;
        }

        Votes[i].vote = Cities[i].city_info.get_vote;
        Votes[i].index = Cities[i].index;
    }

    //? Let's begin with the solution
    //? First we need to sort both vectors
    sort(Cities.begin(), Cities.end());
    sort(Votes.begin(), Votes.end());

    //? From now we can check, staring with i = 0, how many hours
    //? it is going to take for us to get K votes if we get delegates
    //? from the first i cities. In the end in the optimal solution
    //? one of the checked cases must occur.
    //? If we decide on the number of the delegates, then we can lineary
    //? find number of hours needed to get K votes.
    //? So the solution time complexity is O(delegate_num * N) ~= O(N^2)
    
    //? So let's loop over number of delegates that we'll try to aquire
    uint64_t result = 2LL<<60;  //? Some unreachable value
    for (size_t i = 0; i <= (size_t)min(DELEGATE_NUM, K - 1); i++) {
        uint64_t d_delegates_result = acquire_d_delegates(i, K, Cities, Votes);
        result = min(result, d_delegates_result);
    }

    //? Avoiding to use floats
    cout << result / PRECISION << "." << result % PRECISION << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23