oj.uz

Submission #497136

# Submission time Handle Problem Language Result Execution time Memory
497136 2021-12-22T14:08:56 Z tds376 Job Scheduling (CEOI12_jobs) C++11
100 / 100
 578 ms 22616 KB 
//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;
}

Compilation message

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4844 KB Output is correct
2 Correct 56 ms 4956 KB Output is correct
3 Correct 47 ms 4768 KB Output is correct
4 Correct 49 ms 4860 KB Output is correct
5 Correct 49 ms 4836 KB Output is correct
6 Correct 48 ms 4784 KB Output is correct
7 Correct 51 ms 4784 KB Output is correct
8 Correct 46 ms 4804 KB Output is correct
9 Correct 162 ms 4968 KB Output is correct
10 Correct 156 ms 4964 KB Output is correct
11 Correct 49 ms 4888 KB Output is correct
12 Correct 100 ms 7260 KB Output is correct
13 Correct 147 ms 10100 KB Output is correct
14 Correct 221 ms 13048 KB Output is correct
15 Correct 243 ms 14780 KB Output is correct
16 Correct 314 ms 17732 KB Output is correct
17 Correct 367 ms 21828 KB Output is correct
18 Correct 401 ms 21656 KB Output is correct
19 Correct 578 ms 22616 KB Output is correct
20 Correct 374 ms 21700 KB Output is correct