Submission #677525

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677525	2023-01-03T14:04:35 Z	triet123vn	Job Scheduling (CEOI12_jobs)	C++11	40 / 100	283 ms	21716 KB

jobs

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const string FNAME = "jobschedule";
const ll MAXN = 100002, MAXM = 1000000;

struct Job {
  ll numJob, deadline;
  Job() {}
  Job(ll num, ll d) {
    numJob = num;
    deadline = d;
  }
};

struct cmp {
  bool operator() (const Job &a, const Job &b) {
    if (a.deadline == b.deadline) return a.numJob < b.numJob;
    return a.deadline > b.deadline;
  }
};

ll dayJobs[MAXN], tempDay[MAXN], iter[MAXN];
ll n, delays, m;
vector<ll> dayIndex[MAXN];

bool goodJob(ll machineNum) {
  priority_queue<Job, vector<Job>, cmp> q;
  for (ll i = 1; i <= n; ++i) {
    q.push(Job(dayJobs[i], i + delays));

    ll remain = machineNum - q.top().numJob;
    while (q.size() && remain >= 0) {
      q.pop();
      if (q.size()) remain -= q.top().numJob;
    }
    if (q.size() && remain < 0) {
      Job j = q.top();
      j.numJob = -remain;
      q.pop();
      q.push(j);
    }
  }

  return q.empty();
}

ll minMachine(ll l, ll r) {
  if (l == r) {
    goodJob(l);
    return l;
  }
  ll mid = (l + r) / 2;
  if (goodJob(mid)) return minMachine(l, mid);
  return minMachine(mid + 1, r);
}

int main() {
  ios_base::sync_with_stdio(false);
  cout.tie(NULL);
  cin.tie(NULL);

//  freopen((FNAME + ".in").c_str(), "r", stdin);
//  freopen((FNAME + ".out").c_str(), "w", stdout);

  cin >> n >> delays >> m;

  for (ll i = 0; i < m; ++i) {
    ll day;
    cin >> day;
    ++dayJobs[day];
    dayIndex[day].push_back(i+1);
  }

  ll res = minMachine(1, 1000000);
  cout << res << endl;

  priority_queue<Job, vector<Job>, cmp> q;
  for (ll i = 1; i <= n; ++i) {
    q.push(Job(dayJobs[i], i + delays));

    ll remain = res - q.top().numJob;
    while (q.size() && remain >= 0) {
      for (ll i = 0; i < q.top().numJob; ++i) {
        cout << dayIndex[q.top().deadline - delays][iter[q.top().deadline - delays]++] << " ";
      }
      q.pop();
      if (q.size()) remain -= q.top().numJob;
    }
    if (q.size() && remain < 0) {
      if (q.top().numJob + remain) {
        for (ll i = 0; i < q.top().numJob + remain; ++i) {
          cout << dayIndex[q.top().deadline - delays][iter[q.top().deadline - delays]++] << " ";
        }
      }
      Job j = q.top();
      j.numJob = -remain;
      q.pop();
      q.push(j);
    }
    cout << 0 << "\n";
  }

  return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	25 ms	4464 KB	Output isn't correct
2	Incorrect	25 ms	4492 KB	Output isn't correct
3	Incorrect	25 ms	4464 KB	Output isn't correct
4	Incorrect	30 ms	4432 KB	Output isn't correct
5	Incorrect	26 ms	4496 KB	Output isn't correct
6	Incorrect	24 ms	4436 KB	Output isn't correct
7	Incorrect	28 ms	4420 KB	Output isn't correct
8	Incorrect	25 ms	4512 KB	Output isn't correct
9	Incorrect	131 ms	8084 KB	Output isn't correct
10	Incorrect	123 ms	8180 KB	Output isn't correct
11	Correct	16 ms	4348 KB	Output is correct
12	Correct	31 ms	6044 KB	Output is correct
13	Correct	45 ms	9032 KB	Output is correct
14	Correct	77 ms	10620 KB	Output is correct
15	Correct	67 ms	12136 KB	Output is correct
16	Correct	104 ms	14780 KB	Output is correct
17	Correct	149 ms	17800 KB	Output is correct
18	Incorrect	123 ms	17436 KB	Output isn't correct
19	Incorrect	283 ms	21716 KB	Output isn't correct
20	Correct	129 ms	17708 KB	Output is correct