oj.uz

Submission #1011620

# Submission time Handle Problem Language Result Execution time Memory
1011620 2024-06-30T22:00:50 Z Nonoze Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 30056 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;
	}
	cout << flush;
}

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 203 ms 7632 KB Expected EOLN
2 Incorrect 205 ms 7624 KB Expected EOLN
3 Incorrect 215 ms 7708 KB Expected EOLN
4 Incorrect 223 ms 8140 KB Expected EOLN
5 Incorrect 201 ms 8220 KB Expected EOLN
6 Incorrect 211 ms 8220 KB Expected EOLN
7 Incorrect 223 ms 7704 KB Expected EOLN
8 Incorrect 195 ms 7668 KB Expected EOLN
9 Incorrect 133 ms 10900 KB Expected EOLN
10 Incorrect 131 ms 10980 KB Expected EOLN
11 Incorrect 73 ms 2896 KB Expected EOLN
12 Incorrect 203 ms 6120 KB Expected EOLN
13 Incorrect 293 ms 8932 KB Expected EOLN
14 Incorrect 357 ms 13712 KB Expected EOLN
15 Incorrect 521 ms 13160 KB Expected EOLN
16 Incorrect 477 ms 16892 KB Expected EOLN
17 Incorrect 647 ms 20872 KB Expected EOLN
18 Execution timed out 1022 ms 21612 KB Time limit exceeded
19 Execution timed out 1010 ms 30056 KB Time limit exceeded
20 Incorrect 644 ms 20876 KB Expected EOLN