oj.uz

Submission #857068

# Submission time Handle Problem Language Result Execution time Memory
857068 2023-10-05T10:49:42 Z rog1gor Let's Win the Election (JOI22_ho_t3) C++14
5 / 100
 3 ms 600 KB 
#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 1000000
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -