Submission #202307

#	Time	Username	Problem	Language	Result	Execution time	Memory
202307		quocnguyen1012	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	412 ms	23672 KiB

jobs

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int N, M, D;
vector<int> add[maxn];
vector<int> res[maxn];

bool check(int v)
{
  deque<pair<int, int>> dq;
  for (int i = 1; i <= N; ++i){
    res[i].clear();
    for (auto & x : add[i]){
      dq.pb(mp(i, x));
    }
    if (dq.size()){
      if (dq.front().fi + D < i) return false;
    }
    int sz = dq.size();
    for (int j = 0; j < min((int)sz, v); ++j){
      int x = dq.front().se;
      res[i].pb(x); dq.pop_front();
    }
  }
  if (dq.size()) return false;
  return true;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> D >> M;
  for (int i = 1; i <= M; ++i){
    int v; cin >> v;
    add[v].pb(i);
  }
  int l = 1, r = M, mid;
  while (l <= r){
    mid = (l + r) / 2;
    if (check(mid)) r = mid - 1;
    else l = mid + 1;
  }
  cout << l << '\n';
  check(l);
  for (int i = 1; i <= N; ++i){
    for (auto & x : res[i]) cout << x << ' ';
    cout << "0\n";
  }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100