Submission #1090984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090984		wrtt	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	249 ms	65536 KiB

jobs

// Dost SEFEROĞLU

#include "bits/stdc++.h"
//#include "windows.h"

#define int long long
#define mx(a, b) ((a) > (b) ? (a) : (b))
#define mn(a, b) ((a) < (b) ? (a) : (b))
constexpr int mod = 1000000007;

int d;
int n;

bool firsttrue(int mid, int a[], int m) {
  if(mid >= m) {
    return 1;
  }
  int currday = 1;
  int i = 0;
  int maxdelay = 0;
  while(i < m && currday <= n) {
    maxdelay=mx(maxdelay, currday-a[i]);
    ++currday;
    i+=mid;
    if(maxdelay > d) return 0;
  }
  return 1;
}

bool customsort(std::pair<int,int> a, std::pair<int,int> b) {
  return a.second < b.second;
}

void solve() {
  int m;
  std::cin>>n>>d>>m;
  int a[m];
  std::unordered_map<int,int> mp;
  for(int i = 0; i < m; ++i) {
    std::cin>>a[i];
    mp[i] = a[i];
  }
  std::vector<std::pair<int,int>> v(mp.begin(), mp.end());
  std::sort(v.begin(), v.end(), customsort);
  std::sort(a,a+m);
  int l = 1; int r = 100001;
  int ans = -1;
  while(l<=r) {
    int mid = (l+r)/2;
    if(firsttrue(mid,a,m)) {
      ans=mid;
      r=mid-1;
    }
    else {
      l=mid+1;
    }
  }
  std::cout<<ans<<"\n";
  int curr = 0;
  for(auto i : v) {
    if(curr==0) {
      std::cout<<i.first+1<<" ";
      ++curr;
    }
    else if(curr%ans == 0) {
      std::cout<<i.first+1<<" 0\n";
    }
    else {
      std::cout<<i.first+1<<" ";
    }
    ++curr;
  }
  for(int i = curr/2; i < n; ++i) {
    std::cout<<0<<"\n";
  }
  //std::cout<<curr<<"\n";
}

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    int t = 1;
    //std::cin >> t;
    while (t--) {
        solve();
    }
    #ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << elapsed.count() << " seconds\n";
    #endif
    return 0;
}

• Subtask 1: 10 / 100