Submission #493392

#	Time	Username	Problem	Language	Result	Execution time	Memory
493392		PikaQ	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	249 ms	20800 KiB

jobs

#include<bits/stdc++.h>
#define int ll
#define forn(i,n) for(int i=0;i<(n);i++)
#define Forn(i,n) for(int i=1;i<=(n);i++)
#define ll long long
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define rz resize
#define vi vector<int>
#define vl vector<long long>
#define vpi vector<pair<int,int> >
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define all(p) p.begin(),p.end()
#define alr(p,q) p+1,p+q+1
#define ull unsigned long long
#define st0(p) memset((p),0,sizeof(p))
#define T(x) ((x)%2 ? s[(x)/2] : '.')
#define lowb(x) x&-x
#define ls(x) (x)*2
#define rs(x) (x)*2+1
using namespace std;
 
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
// template <class T> int max(T a, T ... b) { cout << a << " "; debug(b...);}
#define fail() {cout << "-1\n";return;}
const int INF = 1e9+7;
const int N = 1e6+9;
int n,d,m;
vpi a;
 
bool check(int x){
	int cur = 1,res = x;
	for(auto &i : a){
		if(cur > i.F + d) return 0;
		if(cur < i.F ) cur++,res = x;
		res--;
		if(res == 0) cur++,res = x;
	}
	return 1;
}
 
void out(int x){
	int cur = 1,res = x;
	for(auto &i : a){
		if(cur < i.F || res == 0){
			cout << "0\n";
			cur++,res = x;
		}
		cout << i.S << ' ';
		res--;
	}
	while(cur <= n) cur++,cout << "0\n";
}
void solve(){
	cin >> n >> d >> m;
	a.rz(m);
	forn(i,m) cin >> a[i].F,a[i].S = i+1;
	sort(all(a));
	int lo =1,hi = m;
	while(lo != hi-1){
		int mid = (lo+hi)/2;
		if(check(mid)) hi = mid;
		else lo = mid;
	}
	cout << hi << '\n';
	// Forn(i,n) cout << "0\n";
	out(hi);
}
 
 
 
 
signed main(){
	// USACO("sabotage");
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	

	// int t;
	// cin >> t;
	// while(t--)
		solve();
 
	return 0;
}
 

• Subtask 1: 60 / 100