제출 #493385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493385		PikaQ	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	233 ms	20808 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( 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';
		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: 55 / 100