oj.uz

Submission #1011619

# Submission time Handle Problem Language Result Execution time Memory
1011619 2024-06-30T21:59:58 Z Nonoze Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 30292 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 (auto x: u) cout << x << ' ';
		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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 7628 KB Expected EOLN
2 Incorrect 213 ms 7628 KB Expected EOLN
3 Incorrect 198 ms 7632 KB Expected EOLN
4 Incorrect 201 ms 8140 KB Expected EOLN
5 Incorrect 196 ms 8216 KB Expected EOLN
6 Incorrect 206 ms 8144 KB Expected EOLN
7 Incorrect 190 ms 7720 KB Expected EOLN
8 Incorrect 200 ms 7628 KB Expected EOLN
9 Incorrect 118 ms 11008 KB Expected EOLN
10 Incorrect 132 ms 11188 KB Expected EOLN
11 Incorrect 100 ms 2900 KB Expected EOLN
12 Incorrect 232 ms 6228 KB Expected EOLN
13 Incorrect 329 ms 9044 KB Expected EOLN
14 Incorrect 399 ms 13768 KB Expected EOLN
15 Incorrect 523 ms 13164 KB Expected EOLN
16 Incorrect 474 ms 16888 KB Expected EOLN
17 Incorrect 623 ms 20876 KB Expected EOLN
18 Execution timed out 1025 ms 21676 KB Time limit exceeded
19 Execution timed out 1058 ms 30292 KB Time limit exceeded
20 Incorrect 636 ms 20880 KB Expected EOLN