oj.uz

Submission #563546

# Submission time Handle Problem Language Result Execution time Memory
563546 2022-05-17T12:23:27 Z ArifBillah Job Scheduling (CEOI12_jobs) C++14
100 / 100
 323 ms 24776 KB 
#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define ff first
#define ss second
#define endl "\n"
#define pb(x) push_back(x)
#define pp() pop_back()
#define inf MAX_INT
#define dvg(x) cout<<#x<<" "<<x<<endl;
#define dvg2(x, y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define dvgv(x) cout<<#x<<" { "; for(auto i : x) {cout<<i<<" ";} cout<<"}"<<endl;
#define dvgp(x) cout<<#x" {"<<x.ff<<", "<<x.ss<<"}"<<endl;
int dx[] {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int const N = 1e5 + 10;
vpii v;
vvi ans;
int n, d, m;

bool ok(int x)
{
    int day = 1, machines = 1;
    ans = vvi(n+1, vi());
    for(int i = 0; i < m; i++){
        while(day < v[i].ff) {
            day++;
            machines = 1;
        }
        if(day - v[i].ff > d){
            return 0;
        }
        if(day > n) return 0;
        ans[day].pb(v[i].ss);
        machines++;
        if(machines > x) {
            day++;
            machines = 1;
        }
    }
    return 1;
}
int main()
{
  fastio();
   
  cin>>n>>d>>m;
  v = vpii(m);
  for(int i = 0; i < m; i++){
    cin>>v[i].ff;
    v[i].ss = i + 1;
  }
  sort(v.begin(), v.end());
  int lo = 0, hi = 1e5 + 12;
  while(lo < hi){
    int mid = (hi + lo)/2;
    if(ok(mid))
        hi = mid;
    else
        lo = mid + 1;
  }
  cout<<lo<<endl;
  ok(lo);
  for(int i = 1; i <= n; i++) {
    for(auto j : ans[i]) cout<<j<<" ";
    cout<<0<<endl;
  }

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2760 KB Output is correct
2 Correct 27 ms 2744 KB Output is correct
3 Correct 27 ms 2796 KB Output is correct
4 Correct 27 ms 2740 KB Output is correct
5 Correct 27 ms 2712 KB Output is correct
6 Correct 28 ms 2612 KB Output is correct
7 Correct 27 ms 2720 KB Output is correct
8 Correct 27 ms 2740 KB Output is correct
9 Correct 49 ms 8648 KB Output is correct
10 Correct 49 ms 9392 KB Output is correct
11 Correct 37 ms 2248 KB Output is correct
12 Correct 71 ms 4156 KB Output is correct
13 Correct 103 ms 6632 KB Output is correct
14 Correct 170 ms 9428 KB Output is correct
15 Correct 168 ms 9604 KB Output is correct
16 Correct 220 ms 11984 KB Output is correct
17 Correct 265 ms 16164 KB Output is correct
18 Correct 284 ms 16464 KB Output is correct
19 Correct 323 ms 24776 KB Output is correct
20 Correct 269 ms 16116 KB Output is correct