oj.uz

Submission #202307

# Submission time Handle Problem Language Result Execution time Memory
202307 2020-02-15T08:55:58 Z quocnguyen1012 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 412 ms 23672 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7668 KB Output is correct
2 Correct 34 ms 7668 KB Output is correct
3 Correct 35 ms 7664 KB Output is correct
4 Correct 35 ms 7668 KB Output is correct
5 Correct 36 ms 7668 KB Output is correct
6 Correct 36 ms 7668 KB Output is correct
7 Correct 36 ms 7608 KB Output is correct
8 Correct 37 ms 7600 KB Output is correct
9 Correct 41 ms 7160 KB Output is correct
10 Correct 42 ms 7288 KB Output is correct
11 Correct 37 ms 7164 KB Output is correct
12 Correct 70 ms 9208 KB Output is correct
13 Correct 102 ms 12404 KB Output is correct
14 Correct 154 ms 15736 KB Output is correct
15 Correct 159 ms 16120 KB Output is correct
16 Correct 224 ms 19448 KB Output is correct
17 Correct 266 ms 23672 KB Output is correct
18 Correct 278 ms 22136 KB Output is correct
19 Correct 412 ms 23416 KB Output is correct
20 Correct 268 ms 23672 KB Output is correct