Submission #168580

#	Time	Username	Problem	Language	Result	Execution time	Memory
168580		arnold518	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	321 ms	16888 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, D, M;
int A[MAXN+10];
vector<int> V[MAXN+10];

bool solve(int x)
{
	int i, j;

	queue<pii> Q;
	for(i=1; i<=N; i++)
	{
		for(auto it : V[i]) Q.push({it, i});
		for(j=0; j<x && !Q.empty(); j++)
		{
			if(Q.front().second<i-D) return false;
			Q.pop();
		}
	}
	if(!Q.empty()) return false;
	return true;
}

int main()
{
	int i, j;
	scanf("%d%d%d", &N, &D, &M);
	for(i=1; i<=M; i++)
	{
		int t;
		scanf("%d", &t);
		V[t].push_back(i);
		A[t]++;
	}

	int lo=0, hi=1e6+10;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid)) hi=mid;
		else lo=mid;
	}

	printf("%d\n", hi);
	queue<int> Q;
	for(i=1; i<=N; i++)
	{
		for(auto it : V[i]) Q.push(it);
		for(j=0; j<hi && !Q.empty(); j++) printf("%d ", Q.front()), Q.pop();
		printf("0\n");
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
jobs.cpp:35: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:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100