Submission #253256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
253256	2020-07-27T14:34:34 Z	anubhavdhar	Job Scheduling (CEOI12_jobs)	C++14	34 / 100	437 ms	15992 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 = 10000;//1e5+5;
const ll ROOTN = 320;

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

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

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()].front() + 1) << ' ';
			job[doing.front()].pop();
			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;
		job[j].push(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

34.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	55 ms	8572 KB	Partially correct
2	Partially correct	57 ms	8568 KB	Partially correct
3	Partially correct	58 ms	8572 KB	Partially correct
4	Partially correct	56 ms	8568 KB	Partially correct
5	Partially correct	55 ms	8572 KB	Partially correct
6	Partially correct	55 ms	8568 KB	Partially correct
7	Partially correct	55 ms	8568 KB	Partially correct
8	Partially correct	54 ms	8568 KB	Partially correct
9	Runtime error	14 ms	14080 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	13 ms	14208 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Partially correct	57 ms	7672 KB	Partially correct
12	Partially correct	118 ms	8892 KB	Partially correct
13	Partially correct	174 ms	10232 KB	Partially correct
14	Partially correct	255 ms	9948 KB	Partially correct
15	Partially correct	254 ms	12152 KB	Partially correct
16	Partially correct	347 ms	11256 KB	Partially correct
17	Partially correct	404 ms	12024 KB	Partially correct
18	Partially correct	437 ms	15992 KB	Partially correct
19	Runtime error	12 ms	14080 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Partially correct	412 ms	11996 KB	Partially correct