oj.uz

Submission #775463

# Submission time Handle Problem Language Result Execution time Memory
775463 2023-07-06T12:03:56 Z kirakaminski968 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 257 ms 24072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;

vector<pi> p;
int n,d,m;
int a[1000005];
int v[100005];
vector<int> h[100005];

int f(int x){
    memset(v,0,sizeof(v));
    int head = 0;
    for (int i=0; i<m; i++) {
        head = max(head,p[i].first);
        while(v[head] >= x) head++;
        if(head > p[i].first + d) return 0;
        v[head]++;
    }
    return 1;
}

int main(){
    scanf("%d %d %d",&n,&d,&m);
    for (int i=0; i<m; i++) {
        scanf("%d",&a[i]);
        p.push_back(pi(a[i],i+1));
    }
    sort(p.begin(),p.end());
    int s = 0, e = m;
    while (s != e) {
        int m = (s+e)/2;
        if(f(m)) e = m;
        else s = m+1;
    }
    printf("%d\n",s);
    int head = 0;
    for (int i=0; i<m; i++) {
        head = max(head,p[i].first);
        while(h[head].size()>= s) head++;
        if(head > p[i].first + d) return 0;
        h[head].push_back(p[i].second);
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<h[i].size(); j++) {
            printf("%d ",h[i][j]);
        }
        puts("0");
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:40:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         while(h[head].size()>= s) head++;
      |               ~~~~~~~~~~~~~~^~~~
jobs.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j=0; j<h[i].size(); j++) {
      |                       ~^~~~~~~~~~~~
jobs.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d %d",&n,&d,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5448 KB Output is correct
2 Correct 22 ms 5484 KB Output is correct
3 Correct 22 ms 5388 KB Output is correct
4 Correct 23 ms 5460 KB Output is correct
5 Correct 22 ms 5396 KB Output is correct
6 Correct 22 ms 5476 KB Output is correct
7 Correct 22 ms 5468 KB Output is correct
8 Correct 23 ms 5424 KB Output is correct
9 Correct 30 ms 5568 KB Output is correct
10 Correct 29 ms 5508 KB Output is correct
11 Correct 28 ms 5320 KB Output is correct
12 Correct 57 ms 7696 KB Output is correct
13 Correct 84 ms 10536 KB Output is correct
14 Correct 135 ms 13116 KB Output is correct
15 Correct 138 ms 14296 KB Output is correct
16 Correct 170 ms 16804 KB Output is correct
17 Correct 202 ms 21052 KB Output is correct
18 Correct 234 ms 22052 KB Output is correct
19 Correct 257 ms 24072 KB Output is correct
20 Correct 205 ms 21120 KB Output is correct