Submission #682026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682026	2023-01-15T09:50:53 Z	handlename	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	175 ms	13588 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
//const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
int n,d,m;
vector<int> arr[100001];
void runtc(){
	cin>>n>>d>>m;
	for (int i=1;i<=m;i++){
		int x;
		cin>>x;
		arr[x].pb(i);
	}
	int mini=0,maxi=1e6;
	while (mini+1<maxi){
		int mid=(mini+maxi)/2;
		bool can=true;
		queue<int> q;
		for (int i=1;i<=n;i++){
			for (auto j:arr[i]) q.push(i+d);
			int num=mid;
			while (!q.empty() && num>0){
				q.pop();
				num--;
			}
			if (!q.empty() && q.front()<=i) can=false;
		}
		if (can) maxi=mid;
		else mini=mid;
	}
	cout<<maxi<<'\n';
	queue<int> q;
	for (int i=1;i<=n;i++){
		for (auto j:arr[i]) q.push(j);
		int num=maxi;
		while (!q.empty() && num>0){
			cout<<q.front()<<' ';
			q.pop();
			num--;
		}
		cout<<0<<'\n';
	}
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("moocast.in","r",stdin);
    //freopen("moocast.out","w",stdout);
    //freopen("input1.in","r",stdin);
    //freopen("output1.out","w",stdout);
    //freopen("perfectly_balanced_chapter_1_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tc;
    //cin>>tc;
    tc=1;
    for (int i=1;i<=tc;i++){
        //cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Compilation message

jobs.cpp: In function 'void runtc()':
jobs.cpp:25:14: warning: unused variable 'j' [-Wunused-variable]
   25 |    for (auto j:arr[i]) q.push(i+d);
      |              ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4052 KB	Output is correct
2	Correct	22 ms	4036 KB	Output is correct
3	Correct	20 ms	4052 KB	Output is correct
4	Correct	20 ms	3992 KB	Output is correct
5	Correct	20 ms	4112 KB	Output is correct
6	Correct	21 ms	4048 KB	Output is correct
7	Correct	20 ms	4008 KB	Output is correct
8	Correct	22 ms	4032 KB	Output is correct
9	Correct	41 ms	4044 KB	Output is correct
10	Correct	31 ms	4076 KB	Output is correct
11	Correct	20 ms	3896 KB	Output is correct
12	Correct	40 ms	5020 KB	Output is correct
13	Correct	59 ms	7024 KB	Output is correct
14	Correct	89 ms	8308 KB	Output is correct
15	Correct	106 ms	9052 KB	Output is correct
16	Correct	134 ms	11160 KB	Output is correct
17	Correct	157 ms	13032 KB	Output is correct
18	Correct	151 ms	12736 KB	Output is correct
19	Correct	175 ms	13588 KB	Output is correct
20	Correct	155 ms	13016 KB	Output is correct