oj.uz

Submission #1011622

# Submission time Handle Problem Language Result Execution time Memory
1011622 2024-06-30T22:05:01 Z Nonoze Job Scheduling (CEOI12_jobs) C++17
95 / 100
 1000 ms 30196 KB 
/*
*	Author: Nonoze
*	Created: Sunday 30/06/2024
*/
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long


#ifdef _IN_LOCAL
	#include <bits/DebugTemplate.h>
#else
	#define dbg(...)
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

// #define endl '\n'
#define endlfl '\n' << flush
template<typename T> void read(T& x, bool write=0) { if (write) cout << x << ' '; else cin >> x; }
template<typename T1, typename T2> void read(pair<T1, T2>& p, bool write=0) { read(p.first, write), read(p.second, write); if (write) cout << endl;}
template<typename T> void read(vector<T>& v, bool write=0) { for (auto& x : v) read(x, write); if (write) cout << endl; }
template<typename T1, typename T2> void read(T1& x, T2& y, bool write=0) { read(x, write), read(y, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z, bool write=0) { read(x, write), read(y, write), read(z, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz, bool write=0) { read(x, write), read(y, write), read(z, write), read(zz, write); if (write) cout << endl; }
template<typename T> void print(T x) { read(x, 1); }
template<typename T1, typename T2> void print(T1 x, T2 y) { read(x, y, 1); }
template<typename T1, typename T2, typename T3> void print(T1 x, T2 y, T3 z) { read(x, y, z, 1); }
template<typename T1, typename T2, typename T3, typename T4> void print(T1 x, T2 y, T3 z, T4 zz) { read(x, y, z, zz, 1); }

#define quit(x) return (void)(cout << x << endl)
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, k, m;
vector<pair<int, int>> abase;
vector<vector<int>> a;

bool ok(int x) {
	multiset<int> todo;
	for (int i=0; i<m; i++) {
		for (auto u: a[i]) todo.insert(i);
		for (int t=0; t<x && !todo.empty(); t++) {
			if (*todo.begin()+k<i) return 0;
			todo.erase(todo.begin());
		}
	}
	if (!todo.empty()) return 0;
	return 1;
}


vector<vector<int>> calc(int x) {
	set<pair<int, int>> todo;
	vector<vector<int>> ans;
	for (int i=0; i<m; i++) {
		for (auto u: a[i]) todo.insert({i, u});
		vector<int> now;
		for (int t=0; t<x && !todo.empty(); t++) {
			now.pb(todo.begin()->se+1);
			todo.erase(todo.begin());
		}
		now.pb(0);
		ans.pb(now);
	}
	return ans;
}

void solve() {
	read(m, k, n);
	a.resize(m);
	for (int i=0; i<n; i++) {
		int x; read(x);
		a[x-1].pb(i);
	}
	int ans=n, l=1, r=n;
	while (l<=r) {
		int mid=(l+r)/2;
		if (ok(mid)) ans=mid, r=mid-1;
		else l=mid+1;
	}
	cout << ans << endl;
	auto res=calc(ans);
	for (auto u: res) {
		for (int i=0; i<sz(u); i++) {
			if (i) cout << ' ';
			cout << u[i];
		}
		cout << endl;
	}
}

Compilation message

jobs.cpp: In function 'bool ok(long long int)':
jobs.cpp:73:13: warning: unused variable 'u' [-Wunused-variable]
   73 |   for (auto u: a[i]) todo.insert(i);
      |             ^

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 7704 KB Output is correct
2 Correct 196 ms 7628 KB Output is correct
3 Correct 211 ms 7628 KB Output is correct
4 Correct 215 ms 8400 KB Output is correct
5 Correct 235 ms 8144 KB Output is correct
6 Correct 210 ms 8236 KB Output is correct
7 Correct 219 ms 7628 KB Output is correct
8 Correct 211 ms 7632 KB Output is correct
9 Correct 228 ms 10804 KB Output is correct
10 Correct 223 ms 11448 KB Output is correct
11 Correct 82 ms 2900 KB Output is correct
12 Correct 233 ms 6120 KB Output is correct
13 Correct 280 ms 8940 KB Output is correct
14 Correct 374 ms 13712 KB Output is correct
15 Correct 459 ms 13164 KB Output is correct
16 Correct 448 ms 16784 KB Output is correct
17 Correct 648 ms 20816 KB Output is correct
18 Correct 961 ms 21608 KB Output is correct
19 Execution timed out 1048 ms 30196 KB Time limit exceeded
20 Correct 619 ms 20816 KB Output is correct