제출 #497136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497136		tds376	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	578 ms	22616 KiB

jobs

//https://oj.uz/problem/view/CEOI12_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+d<i)
                return false;
            ans[i].push_back(job[cnt].s);
        }
        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].clear();
    }
    cout<<l<<endl;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=l&&j<ans[i].size(); j++){
            cout<<ans[i][j]<<' ';
        }
        cout<<0<<endl;
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 100 / 100