Submission #253260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
253260	2020-07-27T14:39:15 Z	anubhavdhar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	503 ms	17760 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	51 ms	4628 KB	Output is correct
2	Correct	53 ms	4628 KB	Output is correct
3	Correct	51 ms	4632 KB	Output is correct
4	Correct	52 ms	4628 KB	Output is correct
5	Correct	53 ms	4628 KB	Output is correct
6	Correct	55 ms	4636 KB	Output is correct
7	Correct	56 ms	4676 KB	Output is correct
8	Correct	54 ms	4632 KB	Output is correct
9	Correct	55 ms	5360 KB	Output is correct
10	Correct	62 ms	5232 KB	Output is correct
11	Correct	54 ms	4204 KB	Output is correct
12	Correct	109 ms	5864 KB	Output is correct
13	Correct	164 ms	8116 KB	Output is correct
14	Correct	240 ms	9828 KB	Output is correct
15	Correct	254 ms	10980 KB	Output is correct
16	Correct	346 ms	13144 KB	Output is correct
17	Correct	414 ms	15456 KB	Output is correct
18	Correct	444 ms	16012 KB	Output is correct
19	Correct	503 ms	17760 KB	Output is correct
20	Correct	434 ms	15464 KB	Output is correct