Submission #563546

#	Time	Username	Problem	Language	Result	Execution time	Memory
563546		ArifBillah	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	323 ms	24776 KiB

jobs

#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 / 100