oj.uz

Submission #614736

# Submission time Handle Problem Language Result Execution time Memory
614736 2022-07-31T04:40:36 Z Trytytka Job Scheduling (CEOI12_jobs) C++17
70 / 100
 1000 ms 49828 KB 
// Source: https://usaco.guide/general/io

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

long long n, d, m;
vector <pair<long long, long long>> a;

bool f(long long x){
	long long g;
	multiset<long long> b;
	for (long long i = 0; i < x; i++) b.insert(0);
	for (long long i = 0; i < m; i++){
		g=*b.begin();
		if(g-a[i].first>d||max(g, a[i].first)>n) return 0;
		b.erase(b.find(g));
		b.insert(max(g, a[i].first)+1);
	}
	return 1;
}

int main() {
	long long x=0, y=1;
	cin >> n >> d >> m;
	vector<set<long long>> c(n+1);
	a.resize(m);
	for (long long i = 0; i < m; i++) {cin >> a[i].first; a[i].second=i+1;}
	sort(a.begin(), a.end());
	while(!f(y)) y*=2;
	for (long long i = y/2; i>=1; i/=2){
		while(i+x<=y&&(!f(i+x))) x+=i;
	}
	cout << ++x;
	long long g;
	multiset<long long> b;
	for (long long i = 0; i < x; i++) b.insert(0);
	for (long long i = 0; i < m; i++){
		g=*b.begin();
		b.erase(b.find(g));
		b.insert(max(g, a[i].first)+1);
		c[max(g, a[i].first)].insert(a[i].second);
	}
	cout << endl;
	for (long long i = 1; i <= n; i++){
		for (auto j:c[i]){
			cout << j << ' ';
		}
		cout << 0 << endl;
	}
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 10164 KB Output is correct
2 Correct 802 ms 10188 KB Output is correct
3 Correct 814 ms 10212 KB Output is correct
4 Correct 815 ms 10164 KB Output is correct
5 Correct 872 ms 10416 KB Output is correct
6 Correct 855 ms 10316 KB Output is correct
7 Correct 850 ms 10172 KB Output is correct
8 Correct 803 ms 10288 KB Output is correct
9 Correct 436 ms 12436 KB Output is correct
10 Correct 417 ms 12512 KB Output is correct
11 Correct 152 ms 7372 KB Output is correct
12 Correct 392 ms 14468 KB Output is correct
13 Correct 564 ms 21464 KB Output is correct
14 Correct 538 ms 28940 KB Output is correct
15 Runtime error 899 ms 35532 KB Memory limit exceeded
16 Runtime error 724 ms 42796 KB Memory limit exceeded
17 Execution timed out 1014 ms 49828 KB Time limit exceeded
18 Execution timed out 1067 ms 13784 KB Time limit exceeded
19 Execution timed out 1073 ms 19460 KB Time limit exceeded
20 Execution timed out 1033 ms 49728 KB Time limit exceeded