Submission #1237156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237156		efeg	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	164 ms	20932 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int long long int
#define F first
#define S second 
#define pb push_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define mt make_tuple
#define pqueue priority_queue

typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<iii> viii;
typedef set<int> si;
typedef vector<ii> vii;				
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

void usaco(string name) {
	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}
const int MOD = 1e9 + 7	;
const int inf = 5e5 + 100;


int n,d,m;
vii jobs; 

bool check(int x){
	bool flag = true;
	int idx = 0; 
	for (int i = 1; i <= n; i++){
		if (idx >= m) break; 
		if (i - jobs[idx].F > d) {
			flag = false; 
			break; 
		}
		
		idx += x; 
	}
	return flag; 
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	#ifndef ONLINE_JUDGE
	//	freopen("output.txt","w",stdout);	
	//	freopen("input.txt","r",stdin);
	    clock_t stime = clock();
	#endif

	cin >> n >> d >> m; 
	jobs.assign(m,ii()); 
	for (int i = 0; i < m; i++)  {
		cin >> jobs[i].F;
		jobs[i].S = i+1; 
	} 

	sort(all(jobs)); 
	int s = 1, e = m,ans = m; 
	while (s <= e){
		int m = (s+e) / 2; 
		if (check(m)){
			e = m-1; 
			ans = m; 
		}
		else s = m+1; 
	}
	cout << ans << endl;
	int idx = 0; 
	for (int i = 0; i < n; i++){
		for (int j = 0; j < ans && idx < m; j++){
			cout << jobs[idx].S << " ";
			idx++; 
		}

		cout << 0 << endl; 
	}

    
    #ifndef ONLINE_JUDGE
	//	cout << setprecision(10) << "Time taken: " << (clock() - stime) * 1.0 / CLOCKS_PER_SEC << endl;  
	#endif
	return 0;
}	

Compilation message (stderr)

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

• Subtask 1: 55 / 100