oj.uz

Submission #93987

# Submission time Handle Problem Language Result Execution time Memory
93987 2019-01-14T04:55:01 Z Rakhmand Job Scheduling (CEOI12_jobs) C++14
100 / 100
 338 ms 27432 KB 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const long long MXN = 1e6 + 1;
const long long MNN = 1e5 + 1;
const long long MOD = 998244353;
const long long INF = 1e18;
const long long OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

int n, d, m;
vector<int> v[MNN];
queue<pair<int, int> > t;
vector<int> ans[MNN];

bool isEnough(int x){
	queue<pair<int, int> > test;
	test = t;
	for(int i = 1; i <= n; i++){
		int cnt = x;
		while(!test.empty() && cnt != 0){
			pair<int, int> j = test.front();
			if(j.F + d < i){
				return false;
			}if(j.F > i){
				break;
			}if(i <= j.F + d){
				test.pop();
				cnt--;
			}
		}
	}return true;
}

int main(){
	ios;
	cin >> n >> d >> m;
	for(int i = 1; i <= m; i++){
		int x;
		cin >> x;
		v[x].pb(i);
	}for(int i = 1; i <= n; i++){
		for(int j = 0; j < v[i].size(); j++){
			t.push({i, v[i][j]});
		}
	}int l = 1, r = MXN;
	while(r - l > 1){
		int mid = (r + l) / 2;
		if(isEnough(mid)){
			r = mid;
		}else{
			l = mid;
		}
	}int ans = (isEnough(l) == true ? l : r);
	cout << ans << nl;
	for(int i = 1; i <= n; i++){
		int cnt = ans;
		while(!t.empty() && cnt != 0){
			pair<int, int> j = t.front();
			if(j.F > i){
				break;
			}if(i <= j.F + d){
				cout << j.S << ' ';
				t.pop();
				cnt--;
			}
		}cout << 0 << nl;
	}
	return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
 
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v[i].size(); j++){
                  ~~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7424 KB Output is correct
2 Correct 34 ms 7476 KB Output is correct
3 Correct 33 ms 7468 KB Output is correct
4 Correct 33 ms 7476 KB Output is correct
5 Correct 33 ms 7472 KB Output is correct
6 Correct 33 ms 7476 KB Output is correct
7 Correct 34 ms 7476 KB Output is correct
8 Correct 33 ms 7480 KB Output is correct
9 Correct 48 ms 7528 KB Output is correct
10 Correct 47 ms 7604 KB Output is correct
11 Correct 42 ms 7688 KB Output is correct
12 Correct 83 ms 10136 KB Output is correct
13 Correct 121 ms 13240 KB Output is correct
14 Correct 179 ms 16200 KB Output is correct
15 Correct 221 ms 17912 KB Output is correct
16 Correct 266 ms 21968 KB Output is correct
17 Correct 338 ms 25124 KB Output is correct
18 Correct 323 ms 25384 KB Output is correct
19 Correct 325 ms 27432 KB Output is correct
20 Correct 320 ms 25144 KB Output is correct