Submission #788399

#TimeUsernameProblemLanguageResultExecution timeMemory
788399Sandarach151Job Scheduling (CEOI12_jobs)C++17
100 / 100
165 ms27572 KiB
#include<bits/stdc++.h> using namespace std; bool func(int arr[], int m, int n, int nummachines, int maxdelay){ bool res = true; int curpos = 0; for(int i=1; i<=n; i++){ if(curpos>=m || !res){ break; } else{ int temp=curpos; for(int j=curpos; j<min(curpos+nummachines, m); j++){ if(arr[j]<=i){ temp++; if(i-arr[j]>maxdelay){ res = false; break; } } else{ break; } } curpos = temp; } } return curpos==m && res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, d, m; cin >> n >> d >> m; int arr[m]; for(int i=0; i<m; i++){ cin >> arr[i]; } vector<int> arr2[n]; for(int i=0; i<m; i++){ arr2[arr[i]-1].push_back(i+1); } sort(arr, arr+m); int minmachine = 0; int maxmachine = m; while(minmachine<maxmachine){ int mid = (minmachine+maxmachine)/2; bool res = func(arr, m, n, mid, d); if(!res){ minmachine = mid+1; } else{ maxmachine = mid; } } cout << minmachine << '\n'; vector<pair<int, int>> vect; for(int i=0; i<n; i++){ for(int j=0; j<arr2[i].size(); j++){ vect.push_back({arr2[i][j], i}); } } int pos = 0; for(int i=0; i<n; i++){ int temp = pos; while(pos<min(temp+minmachine, m) && vect[pos].second<=i){ cout << vect[pos].first << ' '; pos++; } cout << 0 << '\n'; } return 0; }

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int j=0; j<arr2[i].size(); j++){
      |                ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...