oj.uz

Submission #455174

# Submission time Handle Problem Language Result Execution time Memory
455174 2021-08-05T15:45:10 Z inluminas Job Scheduling (CEOI12_jobs) C++14
45 / 100
 231 ms 38508 KB 
#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)

const int lmt=1e6+1;
vector<int>adj[lmt];
int n,d,m,cnt[lmt];

bool ok(int sz){
  memset(cnt,0,sizeof cnt);
  for(int i=n;i>0;i--){
    cnt[i]=adj[i].size();
  }
  int r=n;
  for(int i=n;i>0;i--){
    for(r=min(r,i+d);r>i;r--){
      int left=sz-cnt[r];
      left=min(left,cnt[i]);
      cnt[i]-=left;
      cnt[r]+=left;
      continue;
    }
    if(cnt[i]>sz) return false;
  }
  return true;
}

int main(){
  fastio;

  cin>>n>>d>>m;
  for(int i=1;i<=m;i++){
    int a;
    cin>>a;
    adj[a].push_back(i);
  }

  int lo=1,hi=1e9;
  while(hi-lo>1){
    int mid=(lo+hi)>>1;
    if(ok(mid)) hi=mid;
    else lo=mid;
  }
  int pos;
  if(ok(lo)) pos=lo;
  else pos=hi;

  cout<<pos<<endl;
  int r=n;
  for(int i=n;i>0;i--){
    for(r=min(r,i+d);r>i;r--){
      while(adj[r].size()<pos && !adj[i].empty()){
        adj[r].push_back(adj[i].back());
        adj[i].pop_back();
      }
      if(adj[i].empty()) break;
    }
  }

  for(int i=1;i<=n;i++){
    for(int v:adj[i]) cout<<v<<" ";
    cout<<0<<endl;
  }

  return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |       while(adj[r].size()<pos && !adj[i].empty()){
      |             ~~~~~~~~~~~~~^~~~

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 29124 KB Output is correct
2 Correct 40 ms 29088 KB Output is correct
3 Correct 41 ms 29140 KB Output is correct
4 Correct 41 ms 29136 KB Output is correct
5 Correct 41 ms 29120 KB Output is correct
6 Correct 40 ms 29156 KB Output is correct
7 Correct 41 ms 29124 KB Output is correct
8 Correct 41 ms 29132 KB Output is correct
9 Correct 66 ms 29124 KB Output is correct
10 Incorrect 66 ms 29116 KB Output isn't correct
11 Incorrect 40 ms 28844 KB Output isn't correct
12 Incorrect 62 ms 30020 KB Output isn't correct
13 Incorrect 82 ms 31832 KB Output isn't correct
14 Runtime error 112 ms 33296 KB Memory limit exceeded
15 Runtime error 122 ms 34076 KB Memory limit exceeded
16 Runtime error 157 ms 35780 KB Memory limit exceeded
17 Runtime error 207 ms 38244 KB Memory limit exceeded
18 Runtime error 179 ms 37700 KB Memory limit exceeded
19 Runtime error 231 ms 38508 KB Memory limit exceeded
20 Runtime error 181 ms 38148 KB Memory limit exceeded