oj.uz

Submission #455162

# Submission time Handle Problem Language Result Execution time Memory
455162 2021-08-05T15:22:48 Z shahriarkhan Job Scheduling (CEOI12_jobs) C++14
60 / 100
 263 ms 20380 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 = n ;
    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)
            {
                if(cur>n)
                {
                    bad = 1 ;
                    break ;
                }
                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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6800 KB Output isn't correct
2 Incorrect 26 ms 6792 KB Output isn't correct
3 Incorrect 26 ms 6860 KB Output isn't correct
4 Incorrect 30 ms 6868 KB Output isn't correct
5 Incorrect 26 ms 6840 KB Output isn't correct
6 Incorrect 26 ms 6844 KB Output isn't correct
7 Incorrect 28 ms 6784 KB Output isn't correct
8 Incorrect 26 ms 6776 KB Output isn't correct
9 Correct 35 ms 7180 KB Output is correct
10 Correct 39 ms 7176 KB Output is correct
11 Correct 31 ms 6980 KB Output is correct
12 Correct 59 ms 8712 KB Output is correct
13 Correct 85 ms 11592 KB Output is correct
14 Correct 133 ms 13320 KB Output is correct
15 Correct 140 ms 13580 KB Output is correct
16 Correct 195 ms 15908 KB Output is correct
17 Correct 227 ms 20348 KB Output is correct
18 Correct 225 ms 19404 KB Output is correct
19 Correct 263 ms 20292 KB Output is correct
20 Correct 227 ms 20380 KB Output is correct