Submission #544489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544489	2022-04-02T06:01:22 Z	cig32	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	568 ms	21484 KB

jobs

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
//#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
void solve(int tc) {
  int n, d, m;
  cin >> n >> d >> m;
  vector<int> a[n+1];
  for(int i=1; i<=m; i++) {
    int p;
    cin >> p;
    a[p].push_back(i);
  }
  int lb = 1, rb = 1e9;
  while(lb < rb) {
    int mid = (lb + rb) >> 1;
    queue<pair<int, int> > jobs;
    bool ok = 1;
    for(int i=1; i<=n; i++) {
      for(int x: a[i]) jobs.push({x, i});
      for(int j=1; j<=mid; j++) {
        if(jobs.size()) {
          ok &= (i - jobs.front().second <= d);
          jobs.pop();
        }
        else break;
      }
    }
    if(ok) {
      rb = mid;
    }
    else {
      lb = mid + 1;
    }
  }
  vector<int> fuck[n+1];
  queue<pair<int, int> > jobs;
  for(int i=1; i<=n; i++) {
    for(int x: a[i]) jobs.push({x, i});
    for(int j=1; j<=lb; j++) {
      if(jobs.size()) {
        fuck[i].push_back(jobs.front().first);
        jobs.pop();
      }
      else break;
    }
  }
  cout << lb << "\n";
  for(int i=1; i<=n; i++) {
    for(int x: fuck[i]) cout << x << " ";
    cout << "0\n";
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	4552 KB	Output is correct
2	Correct	68 ms	4604 KB	Output is correct
3	Correct	73 ms	4584 KB	Output is correct
4	Correct	75 ms	4636 KB	Output is correct
5	Correct	81 ms	4568 KB	Output is correct
6	Correct	68 ms	4636 KB	Output is correct
7	Correct	66 ms	4568 KB	Output is correct
8	Correct	65 ms	4660 KB	Output is correct
9	Correct	88 ms	8508 KB	Output is correct
10	Correct	72 ms	8544 KB	Output is correct
11	Correct	67 ms	3572 KB	Output is correct
12	Correct	122 ms	5252 KB	Output is correct
13	Correct	167 ms	8120 KB	Output is correct
14	Correct	275 ms	10472 KB	Output is correct
15	Correct	281 ms	9992 KB	Output is correct
16	Correct	409 ms	12728 KB	Output is correct
17	Correct	486 ms	17272 KB	Output is correct
18	Correct	494 ms	16440 KB	Output is correct
19	Correct	568 ms	21484 KB	Output is correct
20	Correct	474 ms	17256 KB	Output is correct