Submission #714997

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
714997	2023-03-25T17:02:06 Z	lumid	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	239 ms	24152 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	188 ms	2880 KB	Output is correct
2	Correct	172 ms	2820 KB	Output is correct
3	Correct	154 ms	2820 KB	Output is correct
4	Correct	172 ms	2820 KB	Output is correct
5	Correct	156 ms	2824 KB	Output is correct
6	Correct	145 ms	2828 KB	Output is correct
7	Correct	152 ms	2872 KB	Output is correct
8	Correct	151 ms	2824 KB	Output is correct
9	Correct	30 ms	3048 KB	Output is correct
10	Correct	31 ms	3012 KB	Output is correct
11	Correct	28 ms	2924 KB	Output is correct
12	Correct	55 ms	5604 KB	Output is correct
13	Correct	97 ms	9724 KB	Output is correct
14	Correct	103 ms	11212 KB	Output is correct
15	Correct	191 ms	13520 KB	Output is correct
16	Correct	164 ms	19404 KB	Output is correct
17	Correct	228 ms	19408 KB	Output is correct
18	Correct	239 ms	21200 KB	Output is correct
19	Correct	235 ms	24152 KB	Output is correct
20	Correct	189 ms	19248 KB	Output is correct