Submission #467549

#TimeUsernameProblemLanguageResultExecution timeMemory
467549IlsiyaJob Scheduling (CEOI12_jobs)C++17
100 / 100
692 ms31296 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vll; typedef long double ld; #define F first #define S second ll n, d, m; pair<ll, ll> jobs[1000000]; bool cmp(pair<ll, ll> i, pair<ll, ll> j) { if (i.F == j.F) return i.S < j.S; else return i.F < j.F; } bool f(ll x) { ll numb = 0; for (ll i = 1; i <= n; i++) { for (ll j = 0; j < x; j++) { if (jobs[numb].F > i) { break; } if (jobs[numb].F + d >= i) { numb++; } else { return false; } if (numb + 1 == m) { return true; } } } return false; } int main() { cin >> n >> d >> m; for (ll i = 0; i < m; i++) { cin >> jobs[i].F; jobs[i].S = i + 1; } sort(jobs, jobs + m); ll start = 0, end = m, mid = 0; while (start + 1 < end) { mid = (start + end) / 2; if (f(mid)) { end = mid; } else { start = mid; } } cout << end << "\n"; vll ans[n]; ll p1 = 0; for (ll i = 1; i <= n; i++) { for (ll j = 0; j < end; j++) { if (jobs[p1].F > i) { break; } if (jobs[p1].F + d >= i) { ans[i - 1].push_back(jobs[p1].S); p1++; } } } for (ll i = 0; i < n; i++) { for (ll j = 0; j < ans[i].size(); j++) { cout << ans[i][j] << " "; } cout << "0" << "\n"; } }

Compilation message (stderr)

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