Submission #319824

#	Time	Username	Problem	Language	Result	Execution time	Memory
319824		gustason	Hokej (COCI17_hokej)	C++14	0 / 120	109 ms	11204 KiB

hokej

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int t = 0;
struct PlayerQueue {
    int endr, qual, id;
    bool operator<(PlayerQueue other) const {
        return qual < other.qual;
    }
};
struct PlayerSet {
    int endr, joined, qual, id;
    bool operator<(PlayerSet other) const {
        if (joined == other.joined && endr != other.endr) {
            return endr < other.endr;
        }
        if (endr == other.endr && joined != other.joined) {
            return joined < other.joined;
        }
        if (joined == other.joined && endr == other.endr) {
            if (qual == other.qual) {
                return id < other.id;
            }
            return qual < other.qual;
        }
        return (endr - (t - joined)) < (other.endr - (t - joined));
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int dur, n;
    cin >> dur >> n;
    set<PlayerSet> s; // players sorted in order of when they'll leave
    priority_queue<PlayerQueue> q; // the next player in line to be substituted in the game

    for(int i = 1; i <= n; i++) {
        int quality, endurance;
        cin >> quality >> endurance;
        q.push({endurance, quality, i});
    }

    vector<int> starters;
    for(int i = 0; i < 6; i++) {
        PlayerQueue player = q.top();
        s.insert({player.endr, 0, player.qual, player.id});
        starters.push_back(player.id);
        q.pop();
        //cout << q.top().qual << " " << q.top().endr << " " << q.top().id << "\n";
    }

    ll Z = 0;
    vector<array<int, 3>> v;

    while(1) {
        auto it = s.begin();
        t = (*it).joined + (*it).endr;
        if (t >= dur) break; // game ends
        Z += (*it).qual * (*it).endr;
        // change to the best player that isn't tired
        PlayerQueue newPlayer = q.top();
        q.pop();
        array<int, 3> change = {t, (*it).id, newPlayer.id};
        v.push_back(change);
        s.erase(it);
        s.insert({newPlayer.endr, t, newPlayer.qual, newPlayer.id});
    }

    for(auto i : s) {
        Z += (dur - i.joined) * i.qual;
    }
    cout << Z << "\n";

    for(int i : starters) {
        cout << i << " ";
    }
    cout << "\n";
    cout << v.size() << "\n";
    for(auto i : v) {
        cout << i[0] << " " << i[1] << " " << i[2] << "\n";
    }
//    for(auto i : s) {
//        cout << i.endr << " " << i.joined << " " << i.qual << " " << i.id << "\n";
//    }
    return 0;
}
//~ check for overflows

• Subtask 1: 0 / 120