Submission #974917

#	Time	Username	Problem	Language	Result	Execution time	Memory
974917		coolsentenceidontremember	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	349 ms	30656 KiB

jobs

#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 (stderr)

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 / 100