oj.uz

Submission #168580

# Submission time Handle Problem Language Result Execution time Memory
168580 2019-12-14T00:14:47 Z arnold518 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 321 ms 16888 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4496 KB Output is correct
2 Correct 43 ms 4364 KB Output is correct
3 Correct 43 ms 4416 KB Output is correct
4 Correct 43 ms 4416 KB Output is correct
5 Correct 43 ms 4344 KB Output is correct
6 Correct 44 ms 4364 KB Output is correct
7 Correct 43 ms 4368 KB Output is correct
8 Correct 43 ms 4512 KB Output is correct
9 Correct 44 ms 4404 KB Output is correct
10 Correct 44 ms 4476 KB Output is correct
11 Correct 38 ms 4216 KB Output is correct
12 Correct 73 ms 5880 KB Output is correct
13 Correct 106 ms 8108 KB Output is correct
14 Correct 169 ms 10176 KB Output is correct
15 Correct 174 ms 11020 KB Output is correct
16 Correct 244 ms 13696 KB Output is correct
17 Correct 303 ms 16120 KB Output is correct
18 Correct 289 ms 15692 KB Output is correct
19 Correct 321 ms 16888 KB Output is correct
20 Correct 290 ms 16220 KB Output is correct