oj.uz

Submission #1011623

# Submission time Handle Problem Language Result Execution time Memory
1011623 2024-06-30T22:06:32 Z Nonoze Job Scheduling (CEOI12_jobs) C++17
40 / 100
 585 ms 29724 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) {
	unordered_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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7612 KB Output is correct
2 Correct 102 ms 7500 KB Output is correct
3 Correct 110 ms 7500 KB Output is correct
4 Correct 107 ms 7732 KB Output is correct
5 Correct 124 ms 7732 KB Output is correct
6 Correct 111 ms 7500 KB Output is correct
7 Correct 110 ms 7492 KB Output is correct
8 Correct 101 ms 7572 KB Output is correct
9 Incorrect 131 ms 11380 KB Output isn't correct
10 Incorrect 154 ms 10764 KB Output isn't correct
11 Incorrect 45 ms 2876 KB Output isn't correct
12 Incorrect 87 ms 5344 KB Output isn't correct
13 Incorrect 136 ms 9044 KB Output isn't correct
14 Incorrect 193 ms 11688 KB Output isn't correct
15 Incorrect 226 ms 13392 KB Output isn't correct
16 Incorrect 283 ms 16768 KB Output isn't correct
17 Incorrect 370 ms 20428 KB Output isn't correct
18 Incorrect 440 ms 21368 KB Output isn't correct
19 Incorrect 585 ms 29724 KB Output isn't correct
20 Incorrect 361 ms 20608 KB Output isn't correct