제출 #1274572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274572		k12_khoi	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	85 ms	13656 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e5+5;

int n,D,request,x,l,r,mid,res,remain;
vector <int> pos[N];
deque <int> dq;

bool check(int mid)
{
    int remain;
    queue <pii> q;

    for (int i=1;i<=n;i++)
    {
        q.push(make_pair(i,pos[i].size()));

        remain=mid;
        while (!q.empty())
        {
            x=min(remain,q.front().Y);
            remain-=x;
            q.front().Y-=x;

            if (q.front().Y==0) q.pop();
            if (remain==0) break;
        }

        if (!q.empty() and q.front().X<=i-D) return false;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> D >> request;
    for (int i=1;i<=request;i++)
    {
        cin >> x;
        pos[x].push_back(i);
    }

    l=1;
    r=1e9;
    res=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (check(mid))
        {
            r=mid-1;
            res=mid;
        }
        else l=mid+1;
    }


    cout << res << '\n';

    dq.clear();
    for (int i=1;i<=n;i++)
    {
        for (int j:pos[i])
        dq.push_back(j);

        remain=res;
        while (!dq.empty() and remain)
        {
            remain--;
            cout << dq.front() << ' ';
            dq.pop_front();
        }

        cout << 0 << '\n';
    }
}

• Subtask 1: 100 / 100