#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define inf 1e18
#define ff first
#define ss second
#define mod 1000000007
bool helper(vector<pair<ll,ll>> &jobs,vector<vector<ll>> &ans,ll n, ll d, ll m, ll mid){
/*
Out here we need to count all the jobs that have frequency above
0 and need to be processed with following mid machines.
*/
auto temp = jobs;
vector<ll> machines(mid, 0);
// Initially all the machines are unoccupied.
vector<ll> days(m+1,0);
// we also need to maintain the no of days it took the job to complete.
int i = 1;
int j = 0;
int count = 0;
vector<vector<ll>> res;
while(i<=m){
count++;
vector<ll> t;
while(i<=m&&j<mid){
if(temp[i].first>0){
//reduce the frequency
temp[i].first--;
t.push_back(jobs[i].second);
//update the counter of intital date
//if not updated
if(days[temp[i].second]==0){
days[temp[i].second]=count;
}
//update the res vector
// if frequency ends, then update the total days
if(temp[i].first==0){
if(count-days[temp[i].second]>d)
return false;
else
days[temp[i].second] = count - days[temp[i].second];
i++;
}
j++;
}else{
i++;
}
}
t.push_back(0);
res.push_back(t);
j=j%mid;
}
if(count>n)
return false;
ans = res;
return true;
}
void binarySearch(vector<pair<ll,ll>> &jobs, vector<vector<ll>> res,ll n, ll d, ll m){
/*
We need to find the minimum number of machines such
that no job has to wait for more than 'd' days
since its commencement.
*/
ll l = 1;
ll r = m;
ll ans;
while(l<=r){
ll mid = l + (r-l)/2;
bool check = helper(jobs,res,n,d,m,mid);
if(check){
ans = mid;
r = mid-1;
}else{
l = mid+1;
}
}
cout<<ans<<endl;
while(res.size()<n){
res.push_back({0});
}
for(int i = 0;i<res.size();i++){
for(int j = 0;j<res[i].size();j++){
cout<<res[i][j]<<" ";
}
cout<<endl;
}
}
void solve(){
ll n,d,m;
cin>>n>>d>>m;
vector<pair<ll,ll>> jobs(m+1);
vector<vector<ll>> ans;
for(int i = 0;i<m;i++){
ll x;
cin>>x;
jobs[x].first++;
jobs[x].second = x;
}
sort(jobs.begin(),jobs.end());
binarySearch(jobs,ans, n, d, m);
}
int main()
{
int t=1;
//cin>>t;
while(t--)
{
solve();
}
return 0;
}
Compilation message
jobs.cpp: In function 'void binarySearch(std::vector<std::pair<long long int, long long int> >&, std::vector<std::vector<long long int> >, long long int, long long int, long long int)':
jobs.cpp:105:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
105 | while(res.size()<n){
| ~~~~~~~~~~^~
jobs.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i = 0;i<res.size();i++){
| ~^~~~~~~~~~~
jobs.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int j = 0;j<res[i].size();j++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
7296 KB |
Expected EOLN |
| 2 |
Incorrect |
56 ms |
7244 KB |
Expected EOLN |
| 3 |
Incorrect |
55 ms |
7324 KB |
Expected EOLN |
| 4 |
Incorrect |
51 ms |
7292 KB |
Expected EOLN |
| 5 |
Incorrect |
50 ms |
7344 KB |
Expected EOLN |
| 6 |
Incorrect |
51 ms |
7332 KB |
Expected EOLN |
| 7 |
Incorrect |
54 ms |
7432 KB |
Expected EOLN |
| 8 |
Incorrect |
65 ms |
7320 KB |
Expected EOLN |
| 9 |
Incorrect |
171 ms |
11240 KB |
Output isn't correct |
| 10 |
Incorrect |
180 ms |
11244 KB |
Output isn't correct |
| 11 |
Incorrect |
71 ms |
7844 KB |
Output isn't correct |
| 12 |
Incorrect |
114 ms |
15504 KB |
Expected EOLN |
| 13 |
Incorrect |
160 ms |
22912 KB |
Output isn't correct |
| 14 |
Incorrect |
277 ms |
31548 KB |
Expected EOLN |
| 15 |
Runtime error |
251 ms |
37948 KB |
Memory limit exceeded |
| 16 |
Runtime error |
387 ms |
46764 KB |
Memory limit exceeded |
| 17 |
Runtime error |
494 ms |
54700 KB |
Memory limit exceeded |
| 18 |
Runtime error |
466 ms |
61424 KB |
Memory limit exceeded |
| 19 |
Runtime error |
623 ms |
65536 KB |
Memory limit exceeded |
| 20 |
Runtime error |
470 ms |
54824 KB |
Memory limit exceeded |
