Submission #257207

#	Time	Username	Problem	Language	Result	Execution time	Memory
257207		Lawliet	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	207 ms	13816 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;
const int MAXM = 1000010;

int n, m, d;

int sQtd[MAXN];

vector<int> day[MAXN];

bool test(lli k)
{
	lli mn = 0;

	for(int i = 1 ; i <= n ; i++)
	{
		lli curValue = sQtd[i] - k*i - k*d;
		if( curValue > mn ) return false;

		mn = min( mn , sQtd[i] - k*i );
	}

	return true;
}

int bs()
{
	int l = 1;
	int r = m;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( test( m ) ) r = m;
		else l = m + 1;
	}

	return r;
}

int main()
{
	scanf("%d %d %d",&n,&d,&m);

	for(int i = 1 ; i <= m ; i++)
	{
		int d;
		scanf("%d",&d);

		day[d].push_back( i );
	}

	for(int i = 1 ; i <= n ; i++)
		sQtd[i] = sQtd[i - 1] + (int)day[i].size();

	int ans = bs();

	printf("%d\n",ans);

	queue<int> cur;

	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 0 ; j < (int)day[i].size() ; j++)
			cur.push( day[i][j] );

		for(int k = 1 ; k <= ans && !cur.empty() ; k++)
		{
			printf("%d ",cur.front());
			cur.pop();
		}

		printf("0\n");
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d);
   ~~~~~^~~~~~~~~

• Subtask 1: 100 / 100