32512023-02-23 12:12:58TuruTamasÜgyfélszolgálat (45)cpp17Wrong answer 16/4575ms10536 KiB
#include <bits/stdc++.h>


using namespace std;
#define pii pair<long long, long long>

long long N, M, lines_read = 0;
queue<pii> sor;

pii next() {
    if (sor.empty()) {
        pii r;
        cin >> r.first >> r.second;
        // cout << "read to main " << r.first << " " << r.second << "\n";
        lines_read++;
        return r;
    }
    pii r = sor.front();
    sor.pop();
    return r;
}

long long count(long long ido) {
    if (lines_read == N) return sor.size();
    pii t;
    cin >> t.first >> t.second;
    // cout << "read to queue " << t.first << " " << t.second << "\n";
    sor.push(t);
    lines_read++;
    while (lines_read <= N && t.first < ido)
    {
        cin >> t.first >> t.second;
        lines_read++;
        sor.push(t);
        // cout << "read to queue " << sor.front().first << " " << sor.front().second << "\n";
    }
    return sor.size();
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> M >> N;
    priority_queue<pii, vector<pii>, greater<pii>> pultok;
    priority_queue<long long, vector<long long>, greater<long long>> szabad;
    vector<long long> out;
    long long max_count = 0, max_wait = 0;
    for (size_t i = 1; i < M+1; i++)
    {
        pultok.push({0, i});
    }
    for (size_t n = 0; n < N; n++)
    {
        
        pii pali = next();
        // cout << n << ": " << pali.first << " " << pali.second << "\n";
        // // cout << pultok.top().first << " " << pultok.top().second << " " << pali.first << " " << pultok.size() << endl;
        while (!pultok.empty() && pultok.top().first <= pali.first)
        {
            // cout << "sz: " << pultok.top().second << " " << pultok.top().first << "\n";
            szabad.push(pultok.top().second);
            pultok.pop();
        }

        if (!szabad.empty()) {
            // cout << "pult push: " << pali.first + pali.second << " " << szabad.top() << "\n";
            out.push_back(szabad.top());
            pultok.push({pali.first + pali.second, szabad.top()});
            szabad.pop();
        }
        else {
            long long elso = pultok.top().first;
            max_wait = max(max_wait, elso-pali.first);
            max_count = max(max_count, count(elso));
            // cout << "nincs sz\n";
            while (pultok.top().first == elso && !pultok.empty()) 
            {
                // cout << "\tsz push: " << pultok.top().second << " " << pultok.top().first << "\n";
                szabad.push(pultok.top().second);
                pultok.pop();
            }
            // cout << "pultok push: " << elso + pali.second << " " << szabad.top() << "\n";
            pultok.push({elso + pali.second, szabad.top()});
            out.push_back(szabad.top());
            szabad.pop();
        }
    }
    while (pultok.size() > 1) pultok.pop();
    cout << pultok.top().first << " " << max_wait << " " << max_count << "\n"; 
    for (long long x : out) cout << x << "\n";
}
SubtaskSumTestVerdictTimeMemory
base16/45
1Accepted0/03ms1828 KiB
2Accepted0/028ms4256 KiB
3Accepted2/23ms2260 KiB
4Accepted2/23ms2352 KiB
5Wrong answer0/23ms2356 KiB
6Wrong answer0/23ms2592 KiB
7Wrong answer0/23ms2560 KiB
8Wrong answer0/265ms8516 KiB
9Wrong answer0/261ms9576 KiB
10Partially correct1/270ms8940 KiB
11Wrong answer0/264ms8936 KiB
12Wrong answer0/264ms9152 KiB
13Wrong answer0/263ms10072 KiB
14Wrong answer0/267ms9364 KiB
15Wrong answer0/263ms9880 KiB
16Wrong answer0/261ms10536 KiB
17Wrong answer0/263ms10452 KiB
18Wrong answer0/261ms10452 KiB
19Accepted2/275ms9676 KiB
20Accepted3/375ms9900 KiB
21Partially correct2/468ms9888 KiB
22Accepted4/470ms9936 KiB