Submission #496692

#	Time	Username	Problem	Language	Result	Execution time	Memory
496692		tds376	Job Scheduling (CEOI12_jobs)	C++11	5 / 100	423 ms	20108 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

int n, d, m, res;
pair<int, int>job[1000003];
vector<vector<int>>ans(100003);

bool possible(int numM){
    int cnt=0, td=0;
    for(int i=1; i<=n; i++){
        while(job[cnt+1].f<=i&&td<numM&&cnt<m){
            cnt++; td++;
            if(job[cnt].f+2<i)
                return false;
            ans[i].push_back(job[cnt].s);
            //cout<<ans[i][td];
        }
        res=i;
        if(cnt>=m)
            return true;
        td=0;
    }
    return false;
}

int main(){
    cin>>n>>d>>m;
    for(int i=1; i<=m; i++){
        cin>>job[i].f;
        job[i].s=i;
    }
    sort(job+1, job+m+1);
    int l=1, r=m;
    while(l<=r){
        int mid=(l+r)/2;
        bool temp=possible(mid);
        if(temp){
            r=mid-1;
        }else{
            l=mid+1;
        }
        if(l>r)
            break;
        for(int i=1; i<=res; i++)
            //ans[i].assign(mid, 0);
            ans[i].clear();
    }
    cout<<l<<endl;
    for(int i=1; i<=res; i++){
        for(int j=0; j<=l&&j<ans[i].size(); j++){
            cout<<ans[i][j]<<' ';
        }
        cout<<0<<endl;
    }
    //cout<<0<<endl<<0<<endl;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 100