Submission #714997

#	Time	Username	Problem	Language	Result	Execution time	Memory
714997		lumid	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	239 ms	24152 KiB

jobs

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include <climits>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
#define inp(n, a) vector<ll> a;for(int i=0;i<n;i++){ll now;cin>>now;a.pb(now);}
#define all(a) a.begin(),a.end()
#define show(a) for(long long i=0;i<(long long)(a.size()-1);i++)cout<<a[i]<<' ';cout<<a[a.size()-1];

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll sum2(ll a, ll l, ll n){return (n*(a+l))/2;}
ll ceil2(ll a, ll b){return (a+b-1)/b;}

ll n,d,m;
vector<pll> a;

bool ok(ll x) {
	if(x>m)return true;
	ll day=1,ind=0;
	while(day<=n){
		for(ll i=0;i<x;i++){
			if(a[ind].fi>day)break;
			if(day-a[ind].fi>d)return false;
			ind++;
			if(ind==m)return true;
		}
		day++;
	}
	return true;
}

ll bs() {
	ll x=-1;
	for(ll b=20;b>=1;b/=2){
		while(!ok(x+b))x+=b;
	}
	return ++x;
}

void solve() {
	cin>>n>>d>>m;
	for(int i=0;i<m;i++){
		ll now;cin>>now;
		a.pb({now,i+1});
	}
	sort(all(a));
	ll ans=bs();
	cout<<ans<<'\n';
	// continue output the list of schedule
	ll day=1,ind=0;
	while(day<=n){
		for(ll i=0;i<ans;i++){
			if(ind==m)break;
			if(a[ind].fi>day)break;
			cout<<a[ind].se<<' ';
			ind++;
		}
		day++;
		cout<<"0\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	solve();
}

• Subtask 1: 100 / 100