oj.uz

Submission #974917

# Submission time Handle Problem Language Result Execution time Memory
974917 2024-05-04T06:56:32 Z coolsentenceidontremember Job Scheduling (CEOI12_jobs) C++17
100 / 100
 349 ms 30656 KB 
#include<bits/stdc++.h>

#pragma GCC optimize("O3")


#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"

using namespace std;

void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}

int n, d, m;

vector<pair<int, int>> job;

pair<bool, vector<vector<int>>> valid(const int &machine){
	vector<vector<int>> ret(n+1);
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= machine; j++){
			if (job[cnt].ff > i) break;
			if (job[cnt].ff + d < i) return {false, {{}}};
			ret[i].push_back(job[cnt++].ss);
			if (cnt == m) return {true, ret};
		}
	}
	return {false, {{}}};
}






int main(){
	setIO();
    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++){
    	int a;
    	cin >> a;
    	job.push_back({a, i});
	}
	vector<vector<int>> res;
	sort(job.begin(), job.end());
	int l = 1, r = m;
	while (l < r){
		int m = l + (r-l)/2;
		pair<bool, vector<vector<int>>> p = valid(m);
		if (p.ff){
			res = p.ss;
			r = m;
		} else l = m+1;
	}
	cout << l << '\n';
	for (int i = 1; i <= n; i++){
		for (const int &a : res[i]) cout << a << ' ';
		cout << 0 << '\n';
	}
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3540 KB Output is correct
2 Correct 19 ms 3544 KB Output is correct
3 Correct 19 ms 3544 KB Output is correct
4 Correct 19 ms 3540 KB Output is correct
5 Correct 19 ms 3544 KB Output is correct
6 Correct 19 ms 3540 KB Output is correct
7 Correct 20 ms 3728 KB Output is correct
8 Correct 19 ms 3532 KB Output is correct
9 Correct 50 ms 9996 KB Output is correct
10 Correct 57 ms 10076 KB Output is correct
11 Correct 29 ms 3544 KB Output is correct
12 Correct 66 ms 6764 KB Output is correct
13 Correct 82 ms 10176 KB Output is correct
14 Correct 143 ms 14524 KB Output is correct
15 Correct 148 ms 15144 KB Output is correct
16 Correct 195 ms 21172 KB Output is correct
17 Correct 221 ms 26420 KB Output is correct
18 Correct 229 ms 27580 KB Output is correct
19 Correct 349 ms 30656 KB Output is correct
20 Correct 227 ms 26156 KB Output is correct