Submission #677523

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677523	2023-01-03T13:57:47 Z	triet123vn	Job Scheduling (CEOI12_jobs)	C++11	40 / 100	370 ms	23296 KB

jobs

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

struct Job {
  int numJob, deadline;
  Job() {}
  Job(int num, int 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;
  }
};

vector<pair<int, int>> logs[MAXN];
int dayJobs[MAXN], tempDay[MAXN], iter[MAXN];
int n, delays, m;
vector<int> dayIndex[MAXN];

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

    int remain = machineNum - q.top().numJob;
    while (q.size() && remain >= 0) {
      logs[i].push_back(make_pair(q.top().numJob, q.top().deadline - delays));
      q.pop();
      if (q.size()) remain -= q.top().numJob;
    }
    if (q.size() && remain < 0) {
      if (q.top().numJob + remain) logs[i].push_back(make_pair(q.top().numJob + remain, q.top().deadline - delays));
      Job j = q.top();
      j.numJob = -remain;
      q.pop();
      q.push(j);
    }
  }

  return q.empty();
}

int minMachine(int l, int r) {
  if (l == r) {
    goodJob(l);
    return l;
  }
  int 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 (int i = 0; i < m; ++i) {
    int day;
    cin >> day;
    ++dayJobs[day];
    dayIndex[day].push_back(i+1);
  }

  cout << minMachine(1, 1000000) << endl;
  for (int i = 1; i <= n; ++i) {
    for (pair<int, int> log: logs[i]) {
//        cout << log.first << " " << log.second << "\n";
        for (int i = 0; i < log.first; ++i) {
          cout << dayIndex[log.second][iter[log.second]++] << " ";
        }
    }
    cout << "0" << endl;
  }

  return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	38 ms	6908 KB	Output isn't correct
2	Incorrect	41 ms	6692 KB	Output isn't correct
3	Incorrect	39 ms	6796 KB	Output isn't correct
4	Incorrect	45 ms	6804 KB	Output isn't correct
5	Incorrect	42 ms	6768 KB	Output isn't correct
6	Incorrect	37 ms	6724 KB	Output isn't correct
7	Incorrect	39 ms	6800 KB	Output isn't correct
8	Incorrect	40 ms	6800 KB	Output isn't correct
9	Incorrect	227 ms	12900 KB	Output isn't correct
10	Incorrect	224 ms	12844 KB	Output isn't correct
11	Correct	19 ms	6100 KB	Output is correct
12	Correct	33 ms	7372 KB	Output is correct
13	Correct	46 ms	9224 KB	Output is correct
14	Correct	89 ms	10588 KB	Output is correct
15	Correct	96 ms	11444 KB	Output is correct
16	Correct	126 ms	13388 KB	Output is correct
17	Correct	135 ms	15052 KB	Output is correct
18	Incorrect	139 ms	15576 KB	Output isn't correct
19	Incorrect	370 ms	23296 KB	Output isn't correct
20	Correct	133 ms	15104 KB	Output is correct