oj.uz

Submission #989367

# Submission time Handle Problem Language Result Execution time Memory
989367 2024-05-28T05:03:18 Z muhammad Feast (NOI19_feast) C++17
0 / 100
 1 ms 348 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

// Function to check if the given max time is feasible
bool feasible(const vector<ll>& work, ll N, ll K, ll max_time) {
    ll cows_used = 0;
    for (ll w : work) {
        cows_used += (w + max_time - 1) / max_time;
        if (cows_used > K) {
            return false;
        }
    }
    return true;
}

// Main function to find the minimum possible maximum time
ll find_min_time(const vector<ll>& work, ll N, ll K) {
    ll left = 1, right = *max_element(work.begin(), work.end());
    while (left < right) {
        ll mid = (left + right) / 2;
        if (feasible(work, N, K, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Function to calculate the distribution of cows
vector<ll> distribute_cows(const vector<ll>& work, ll N, ll K, ll max_time) {
    priority_queue<pair<double, pair<ll, ll>>> pq;
    for (ll i = 0; i < N; ++i) {
        ll cows = 1;
        double time_per_cow = static_cast<double>(work[i]) / cows;
        pq.push({-time_per_cow, {cows, i}});
    }

    ll remaining_cows = K - N;
    while (remaining_cows > 0) {
        auto top = pq.top();
        pq.pop();
        ll cows = top.second.first;
        ll i = top.second.second;
        cows++;
        double time_per_cow = static_cast<double>(work[i]) / cows;
        pq.push({-time_per_cow, {cows, i}});
        remaining_cows--;
    }

    vector<ll> cows_distribution(N);
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        cows_distribution[top.second.second] = top.second.first;
    }

    return cows_distribution;
}

int main() {
    ll N = 30;
    ll K = 200;
    vector<ll> work = {
        500, 29, 217, 48, 6, 3, 5, 15, 256, 358, 57, 21, 67, 41, 303, 24, 17,
        12, 94, 9, 4, 10, 423, 111, 183, 131, 7, 155, 34, 79
    };

    ll min_time = find_min_time(work, N, K);
    vector<ll> cows_distribution = distribute_cows(work, N, K, min_time);

    for (ll cows : cows_distribution) {
        cout << cows << " ";
    }
    cout << endl;

    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

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