# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
455163 | shahriarkhan | Job Scheduling (CEOI12_jobs) | C++14 | 276 ms | 20420 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |