Submission #493327

#	Time	Username	Problem	Language	Result	Execution time	Memory
493327		PikaQ	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	143 ms	39108 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;
vi q[N];

bool check(int x){
	int cur = 1,sum = x;
	Forn(i,n){
		int res = q[i].size();
		if(cur < i){
			cur = i,sum = x;
		}
		while(res){
			res -= sum;
			// debug(cur,sum,res);
			if(res < 0){
				sum = -res;
				res = 0;
			}
			cur++;
			sum = x;
			// debug(cur,sum,res);
			if(cur > i+d) return 0;
		}
	}
	return 1;
}

void out(int x){
	int cur = 1,sum = x;
	Forn(i,n){
		while(cur < i){
			cur++,sum=x;
			cout << "0\n";
		}
		for(auto &j : q[i]){
			cout << j << ' ';
			sum--;
			if(sum == 0){
				cur++;
				sum = x;
				cout << "0\n";
			}
		}
	}
}

void solve(){
	cin >> n >> d >> m;
	int tmp;
	Forn(i,m){
		cin >> tmp;
		q[tmp].pb(i);
	}

	int lo = 0,hi = 2e6;
	while(lo != hi-1){
		int mid = (lo+hi)/2;
		if(check(mid)) hi = mid;
		else lo = mid;
	}	
	cout << hi << '\n';
	out(hi);
	// debug(check(1),check(2),check(3));
}




signed main(){
	// USACO("sabotage");
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif

	// int t;
	// cin >> t;
	// while(t--)
		solve();

	return 0;
}

• Subtask 1: 0 / 100