Submission #951632

#	Time	Username	Problem	Language	Result	Execution time	Memory
951632		doducanh	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	497 ms	30148 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=1e5+7;
vector<int>a[maxn];
vector<int>ans[maxn];
vector<int>ress[maxn];
int n,d,m;
bool check(int limit)
{
    priority_queue<ii,vector<ii>,greater<ii>>q;
    for(int i=1;i<=n;i++)ans[i].clear();
    for(int i=1;i<=n;i++){
        while(ans[i].size()<limit&&q.size()){
            if(i-q.top().fi>d)return false;
            ans[i].push_back(q.top().se);
            q.pop();
        }
        for(int x:a[i]){
            if(ans[i].size()<limit)ans[i].push_back(x);
            else q.push({i,x});
        }
    }
    if(q.size())return false;
    for(int i=1;i<=n;i++){
        ress[i].clear();
        for(int x:ans[i])ress[i].push_back(x);
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        a[x].push_back(i);
    }
    int l=0,r=m;
    int res=m;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            res=m;
            r=m-1;
        }
        else l=m+1;
    }
    cout<<res<<"\n";
    for(int i=1;i<=n;i++){
        for(int x:ress[i])cout<<x<<" ";
        cout<<0<<"\n";
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:17:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         while(ans[i].size()<limit&&q.size()){
      |               ~~~~~~~~~~~~~^~~~~~
jobs.cpp:23:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |             if(ans[i].size()<limit)ans[i].push_back(x);
      |                ~~~~~~~~~~~~~^~~~~~

• Subtask 1: 100 / 100