oj.uz

Submission #455175

# Submission time Handle Problem Language Result Execution time Memory
455175 2021-08-05T15:45:53 Z inluminas Job Scheduling (CEOI12_jobs) C++14
0 / 100
 267 ms 65536 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=2e6+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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 56528 KB Memory limit exceeded
2 Runtime error 71 ms 56520 KB Memory limit exceeded
3 Runtime error 69 ms 56480 KB Memory limit exceeded
4 Runtime error 69 ms 56684 KB Memory limit exceeded
5 Runtime error 70 ms 56516 KB Memory limit exceeded
6 Runtime error 70 ms 56516 KB Memory limit exceeded
7 Runtime error 70 ms 56516 KB Memory limit exceeded
8 Runtime error 70 ms 56504 KB Memory limit exceeded
9 Runtime error 103 ms 56508 KB Memory limit exceeded
10 Runtime error 100 ms 56556 KB Memory limit exceeded
11 Runtime error 71 ms 56152 KB Memory limit exceeded
12 Runtime error 92 ms 57408 KB Memory limit exceeded
13 Runtime error 111 ms 59248 KB Memory limit exceeded
14 Runtime error 148 ms 60716 KB Memory limit exceeded
15 Runtime error 150 ms 61520 KB Memory limit exceeded
16 Runtime error 210 ms 63152 KB Memory limit exceeded
17 Runtime error 206 ms 65456 KB Memory limit exceeded
18 Runtime error 204 ms 65220 KB Memory limit exceeded
19 Runtime error 267 ms 65536 KB Memory limit exceeded
20 Runtime error 213 ms 65500 KB Memory limit exceeded