oj.uz

Submission #455163

# Submission time Handle Problem Language Result Execution time Memory
455163 2021-08-05T15:24:41 Z shahriarkhan Job Scheduling (CEOI12_jobs) C++14
100 / 100
 276 ms 20420 KB 
#include<bits/stdc++.h>
using namespace std ;

const int mx = 1e5 + 5 ;

vector<int> pos[mx] ;

vector<int> ans[mx] ;

int siz[mx] ;

int main()
{
    int n , d , m ;
    scanf("%d%d%d",&n,&d,&m) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        int x ;
        scanf("%d",&x) ;
        pos[x].push_back(i) ;
        ++siz[x] ;
    }
    int low = 1 , high = m ;
    while(low<high)
    {
        int mid = (low+high)/2 , cnt[mx] = {0} , cur = 1 , bad = 0 ;
        for(int i = 1 ; i <= n ; ++i)
        {
            for(int j = 1 ; j <= siz[i] ; ++j)
            {
                while((cur<i) || (cnt[cur]==mid)) ++cur ;
                if((cur-i)>d)
                {
                    bad = 1 ;
                    break ;
                }
                ++cnt[cur] ;
            }
            if(bad) break ;
        }
        if(!bad) high = mid ;
        else low = mid + 1 ;
    }
    int cnt[mx] = {0} , cur = 1 ;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 0 ; j < siz[i] ; ++j)
        {
            while((cur<i) || (cnt[cur]==low)) ++cur ;
            ++cnt[cur] ;
            ans[cur].push_back(pos[i][j]) ;
        }
    }
    printf("%d\n",low) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j : ans[i]) printf("%d ",j) ;
        printf("0\n") ;
    }
    return 0 ;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d%d%d",&n,&d,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d",&x) ;
      |         ~~~~~^~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7036 KB Output is correct
2 Correct 30 ms 6980 KB Output is correct
3 Correct 30 ms 6932 KB Output is correct
4 Correct 31 ms 6972 KB Output is correct
5 Correct 30 ms 6968 KB Output is correct
6 Correct 31 ms 6972 KB Output is correct
7 Correct 32 ms 7032 KB Output is correct
8 Correct 31 ms 6980 KB Output is correct
9 Correct 35 ms 7176 KB Output is correct
10 Correct 36 ms 7132 KB Output is correct
11 Correct 34 ms 7112 KB Output is correct
12 Correct 66 ms 8636 KB Output is correct
13 Correct 98 ms 11592 KB Output is correct
14 Correct 136 ms 13420 KB Output is correct
15 Correct 148 ms 13560 KB Output is correct
16 Correct 208 ms 15800 KB Output is correct
17 Correct 234 ms 20400 KB Output is correct
18 Correct 243 ms 19408 KB Output is correct
19 Correct 276 ms 20404 KB Output is correct
20 Correct 237 ms 20420 KB Output is correct