oj.uz

Submission #120988

# Submission time Handle Problem Language Result Execution time Memory
120988 2019-06-25T21:42:51 Z MB81 Job Scheduling (CEOI12_jobs) C++14
58 / 100
 386 ms 17584 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

queue <pii> q1;
vector <int> v1[maxn];
int n, d, m;

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		v1[x].PB(i + 1);
	}
	int l, r, mid;
	l = 0;
	r = m;
	while (r - l > 1) {
		mid = (l + r) >> 1;
		while(sz(q1)) q1.pop();
		bool ok = 1;
		for (int i = 1; i <= n; i++) {
			if (sz(q1) && q1.front().F < i - d)
				ok = 0;
			for (auto x : v1[i])
				q1.push(MP(i, x));
			for (int t = 0; t < mid && sz(q1); t++)
				q1.pop();
		}
		if (sz(q1))
			ok = 0;
		if (ok)	
			r = mid;
		else
			l = mid;
	}
	cout << r << "\n";
	while(sz(q1)) q1.pop();
	for (int i = 1; i <= n; i++) {
		for (auto x : v1[i])
			q1.push(MP(i, x));
		for (int t = 0; t < mid && sz(q1); t++) {
			cout << q1.front().S << " ";
			q1.pop();
		}
		cout << "0\n";
	}

}

Subtask #1
58.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 4852 KB Partially correct
2 Partially correct 38 ms 4848 KB Partially correct
3 Partially correct 39 ms 4852 KB Partially correct
4 Partially correct 38 ms 4852 KB Partially correct
5 Partially correct 38 ms 4848 KB Partially correct
6 Partially correct 38 ms 4852 KB Partially correct
7 Partially correct 38 ms 4848 KB Partially correct
8 Partially correct 40 ms 4852 KB Partially correct
9 Partially correct 45 ms 4600 KB Partially correct
10 Partially correct 46 ms 4600 KB Partially correct
11 Correct 37 ms 4216 KB Output is correct
12 Correct 75 ms 5836 KB Output is correct
13 Partially correct 114 ms 8008 KB Partially correct
14 Correct 207 ms 10824 KB Output is correct
15 Correct 201 ms 11128 KB Output is correct
16 Correct 265 ms 15236 KB Output is correct
17 Partially correct 386 ms 17580 KB Partially correct
18 Correct 313 ms 15480 KB Output is correct
19 Partially correct 355 ms 16760 KB Partially correct
20 Partially correct 378 ms 17584 KB Partially correct