Submission #1112739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112739		wrtt	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	717 ms	61364 KiB

jobs

#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb emplace_back
#define mx(a, b) ((a) > (b) ? (a) : (b))
#define mn(a, b) ((a) < (b) ? (a) : (b))
#define graph(n) vector<int> g[(n)+1];
constexpr int mod = 1000000007;

void frx(std::string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}

/*
template <typename T, size_t N>
ostream &operator<<(ostream &os, const T (&arr)[N]) {
  os << "[";
  for(size_t i = 0; i < N; ++i) {
    if(i>0) {
      os << ", ";
    }
    os<<arr[i];
  }
  return os << "]";
}
*/

bool firsttrue(int mid, int a[], int m, int d) {
  if(mid >= m) return 1;
  int b[m];
  for(int i = 0; i < m; ++i) {
    b[i] = (i / mid)+1;
  }
  for(int i = 0; i < m; ++i) {
    if((b[i] - a[i]) > d) return 0;
    if(b[i] > m) return 0;
  }
  return 1;
}
void solve() {
  int n,d,m;
  cin>>n>>d>>m;
  int a[m];
  unordered_map<int,unordered_set<int>> mp;
  for(int i = 0; i < m; ++i) {
    cin>>a[i];
    mp[a[i]].insert(i);
  }
  sort(a,a+m);
  int l = 1; int r = 1e6;
  int ans = 1e6;
  while(l<=r) {
    int mid = (l+r)/2;
    if(firsttrue(mid,a,m,d)) {
      r=mid-1;
      ans=mid;
    }
    else {
      l=mid+1;
    }
  }
  cout<<ans<<"\n";
  int cnt = 0;
  bool visited[100001];
  int line = 0;
  memset(visited,0,sizeof(visited));
  for(int i = 0; i < m; ++i) {
    if(!visited[a[i]]) {
    for(int val : mp[a[i]]) {
      cout<<val+1<<" ";
      ++cnt;
      if(cnt==ans) {
        cout<<"0\n";
        ++line;
        cnt=0;
      }
    }
    visited[a[i]] = 1;
    }
  }
  if(cnt!=0) {
    cout<<"0\n";
    ++line;
  }
  for(int i = line; i < n; ++i) {
    cout<<"0\n";
  }
}
  
signed main() {
    std::ios_base::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    //frx("piggyback");
    #ifdef LOCAL  
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    int t = 1;
    //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;  
}

Compilation message (stderr)

jobs.cpp: In function 'void frx(std::string)':
jobs.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100