Submission #638344

#	Time	Username	Problem	Language	Result	Execution time	Memory
638344		NONTAC	Job Scheduling (CEOI12_jobs)	C++11	10 / 100	502 ms	24432 KiB

jobs

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

typedef pair<int,int> ii;

int n,m,d;
ii a[1000000];
vector<vector<int> > ans(100001);
bool ok=false;

bool check(int x)
{
    int j=0;
    for(int i=1;i<=n;i++){
        int cnt=x;
        if(a[j].first> i+d) return false;
        while(cnt && a[j].first <= i+d && j<m){
            cnt--;
            if(ok) ans[i].push_back(a[j].second+1);
            j++;
            if(j==m){
                return true;
            }
        }
    }

    return false;
}

int last_true()
{
    int lo=1, hi=m;
    while(lo<hi){
        int mid=lo + (hi-lo)/2;
        if(check(mid)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }

    ok=true;
    check(lo);

    return lo;
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);


    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].first;
        a[i].second=i;
    }

    sort(a,a+m);

    cout<<last_true()<<endl;

    for(int i=1;i<=n;i++){
        for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
        cout<<0<<endl;
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 100