oj.uz

Submission #537139

# Submission time Handle Problem Language Result Execution time Memory
537139 2022-03-14T15:39:25 Z mgl_diamond Job Scheduling (CEOI12_jobs) C++14
100 / 100
 259 ms 28708 KB 
#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for(int i=l; i<=r; ++i)
#define fod(i, l, r) for(int i=r; i>=l; --i)
#define ll long long 
#define ii pair<ll, ll>
#define fi first
#define se second

template<class T> bool umax(T &a, T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool umin(T &a, T b) { if (a>b) { a=b; return 1; } return 0; }

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const double oo=1e18;
int n, d, m;
vector<ii> stX(1000001);
vector<int> ans[100001];

bool f(int x) {
	for(int day=1, j=1; day<=m && j<=n; ++day)
		for(int i=1; i<=x && j<=n && stX[j].fi<=day; ++i)
			if (day>stX[j++].fi+d)
				return 0;
	return 1;
}

void trace(int x) {
	for(int day=1, j=1; day<=m && j<=n; ++day)
		for(int i=1; i<=x && j<=n && stX[j].fi<=day; ++i)
			ans[day].push_back(stX[j++].se);
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cout.tie(0);
	
	cin >> m >> d >> n;
	for(int i=1; i<=n; ++i) { 
		cin >> stX[i].fi;
		stX[i].se=i;
	}

	sort(stX.begin()+1, stX.begin()+n+1);
	
	//for(int i=1; i<=n; ++i)
	//	cout << stX[i].fi << ' ' << stX[i].se << '\n';
	int lb=1, rb=n+1, mb;
	while (lb<rb) {
		mb=(lb+rb)>>1;
		if (f(mb))
			rb=mb;
		else
			lb=mb+1;
	}

	trace(lb);
	cout << lb << '\n';
	for(int i=1; i<=m; ++i) {
		for(int j: ans[i])
			cout << j << ' ';
		cout << "0\n";
	}
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19412 KB Output is correct
2 Correct 35 ms 19404 KB Output is correct
3 Correct 28 ms 19352 KB Output is correct
4 Correct 25 ms 19404 KB Output is correct
5 Correct 27 ms 19440 KB Output is correct
6 Correct 27 ms 19364 KB Output is correct
7 Correct 28 ms 19448 KB Output is correct
8 Correct 28 ms 19432 KB Output is correct
9 Correct 41 ms 19612 KB Output is correct
10 Correct 35 ms 19616 KB Output is correct
11 Correct 33 ms 19424 KB Output is correct
12 Correct 61 ms 20556 KB Output is correct
13 Correct 100 ms 22308 KB Output is correct
14 Correct 129 ms 23692 KB Output is correct
15 Correct 163 ms 23632 KB Output is correct
16 Correct 176 ms 25108 KB Output is correct
17 Correct 206 ms 28160 KB Output is correct
18 Correct 229 ms 27924 KB Output is correct
19 Correct 259 ms 28708 KB Output is correct
20 Correct 241 ms 28192 KB Output is correct