Submission #253262

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
253262	2020-07-27T14:39:51 Z	anubhavdhar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	268 ms	17756 KB

jobs

#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cerr<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 1e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

int N, M, D;
queue<int> doing, waiting;
vector<int> job[MAXN];
int A[MAXN];
vector<int> V;

inline void tmwst()
{
	int a = 4343, b = 24323;
	while(a != 4344)
	{
		a = __gcd(a, b);
	}
}

inline void init()
{
	while(!doing.empty())	doing.pop();
	while(!waiting.empty())	waiting.pop();
}

inline bool doable(int R)
{
	init();

	int tmp[N+1];
	F0Re(i, N)
		tmp[i] = A[i];

	F0Re(i, N)
	{
		if((!waiting.empty()) and i - (int)waiting.front() > D)
			return false;
		// int L = tmp[i];
		while((!waiting.empty()) and ((int)doing.size() < R))
		{
			doing.push(waiting.front());
			waiting.pop();
		}
		F0R(j, tmp[i])
		{
			if((int)doing.size() < R)
				doing.push(i);
			else
				waiting.push(i);
		}
		while(!doing.empty())	doing.pop();
	}

	return true;
}

inline void solve(int R)
{
	cout<<R<<'\n';

	init();

	int tmp[N+1];
	F0Re(i, N)
		tmp[i] = A[i];

	F0Re(i, N)
	{
		//if((!waiting.empty()) and i - (int)waiting.front() > D)
		// int L = tmp[i];
		while((!waiting.empty()) and ((int)doing.size() < R))
		{
			doing.push(waiting.front());
			waiting.pop();
		}
		F0R(j, tmp[i])
		{
			if((int)doing.size() < R)
				doing.push(i);
			else
				waiting.push(i);
		}
		while(!doing.empty())
		{
			if(job[doing.front()].empty())
				tmwst();
			cout << (job[doing.front()][job[doing.front()].size()-1] + 1) << ' ';
			job[doing.front()].pop_back();
			doing.pop();
		}

		cout<<"0\n";
	}

}

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

	int j, hi, lo, mid;
	cin>>N>>D>>M;

	F0Re(i, N)
		A[i] = 0;


	F0R(i, M)
	{
		cin>>j;
		V.pb(j);
		job[j].push_back(i);
		++A[j];
	}

	lo = 0, hi = M;
	while(lo < hi - 1)
	{
		mid = (hi + lo)/2;
		if(doable(mid))
			hi = mid;
		else
			lo = mid;
	}

	solve(hi);


	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4588 KB	Output is correct
2	Correct	31 ms	4616 KB	Output is correct
3	Correct	31 ms	4588 KB	Output is correct
4	Correct	31 ms	4592 KB	Output is correct
5	Correct	31 ms	4596 KB	Output is correct
6	Correct	29 ms	4596 KB	Output is correct
7	Correct	32 ms	4588 KB	Output is correct
8	Correct	30 ms	4596 KB	Output is correct
9	Correct	37 ms	5360 KB	Output is correct
10	Correct	40 ms	5232 KB	Output is correct
11	Correct	28 ms	4208 KB	Output is correct
12	Correct	62 ms	5868 KB	Output is correct
13	Correct	87 ms	8164 KB	Output is correct
14	Correct	128 ms	9828 KB	Output is correct
15	Correct	129 ms	11108 KB	Output is correct
16	Correct	169 ms	13232 KB	Output is correct
17	Correct	219 ms	15580 KB	Output is correct
18	Correct	251 ms	15844 KB	Output is correct
19	Correct	268 ms	17756 KB	Output is correct
20	Correct	218 ms	15588 KB	Output is correct