답안 #715685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715685 2023-03-27T13:58:20 Z 12345678 Job Scheduling (CEOI12_jobs) C++17
100 / 100
154 ms 16688 KB
#include <bits/stdc++.h>

using namespace std;

int N, D, M, d;
vector<vector<int>> v(100005);

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>N>>D>>M;
    for (int i=1; i<=M; i++)
    {
        cin>>d;
        v[d].push_back(i);
    }
    int l=1, r=M;
    while (l<r)
    {
        int md=(l+r)/2;
        bool can=true;
        deque<pair<int, int>> dq;
        for (int i=1; i<=N; i++)
        {
            if (v[i].size()!=0)
                dq.push_back({i+D, v[i].size()});
            int mc=md;
            while (mc>0&&!dq.empty())
            {
                int cw=dq.front().second;
                if (mc>=cw)
                {
                    mc-=cw;
                    dq.pop_front();
                }
                else
                {
                    int dl=dq.front().first;
                    dq.pop_front();
                    dq.push_front({dl, cw-mc});
                    mc=0;
                    break;
                }
            }
            if (!dq.empty())
            {
                if (dq.front().first<=i)
                {
                    can=false;
                    break;
                }
            }
        }
        if (can)
            r=md;
        else
            l=md+1;
    }
    cout<<l<<'\n';
    queue<int> q;
    for (int i=1; i<=N; i++)
    {
        int left=l;
        for (auto a:v[i])
            q.push(a);
        while (!q.empty()&&left>0)
        {
            left--;
            cout<<q.front()<<' ';
            q.pop();
        }
        cout<<"0\n";
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4308 KB Output is correct
2 Correct 17 ms 4260 KB Output is correct
3 Correct 18 ms 4388 KB Output is correct
4 Correct 15 ms 4308 KB Output is correct
5 Correct 20 ms 4352 KB Output is correct
6 Correct 16 ms 4308 KB Output is correct
7 Correct 17 ms 4356 KB Output is correct
8 Correct 16 ms 4300 KB Output is correct
9 Correct 28 ms 4304 KB Output is correct
10 Correct 29 ms 4324 KB Output is correct
11 Correct 17 ms 4204 KB Output is correct
12 Correct 32 ms 5764 KB Output is correct
13 Correct 57 ms 7900 KB Output is correct
14 Correct 89 ms 9920 KB Output is correct
15 Correct 82 ms 10964 KB Output is correct
16 Correct 127 ms 13388 KB Output is correct
17 Correct 147 ms 15820 KB Output is correct
18 Correct 131 ms 15436 KB Output is correct
19 Correct 154 ms 16688 KB Output is correct
20 Correct 152 ms 15672 KB Output is correct