Submission #763186

#TimeUsernameProblemLanguageResultExecution timeMemory
763186KN200711Job Scheduling (CEOI12_jobs)C++14
20 / 100
255 ms20408 KiB
# include <bits/stdc++.h> using namespace std; int arr[1000001]; vector<int> pos[100001]; int N, D, M; bool cek(int a) { deque<pair<int, int> > d; d.clear(); for(int c=1;c<=N;c++) { d.push_front(make_pair(pos[c].size(), c)); int V = a; while(d.size() && d.back().first <= V) { // if(a == 2) cout<<"V : "<<V<<endl; V -= d.back().first; d.pop_back(); } if(d.size() && d.back().first > V) { d.back().first -= V; } // if(a == 2) cout<<c<<" "<<d.size()<<" "<<d.back().second<<endl; if(d.size() > 0 && d.back().second + D < c) return 0; } return 1; } int main() { scanf("%d %d %d", &N, &D, &M); for(int i=0;i<M;i++) { scanf("%d", &arr[i]); pos[arr[i]].push_back(i); } int lf = 0, rg = 1e6, ans = -1; // cout<<cek(2)<<endl; while(lf <= rg) { int mid = (lf + rg) / 2; if(cek(mid)) { ans = mid; rg = mid - 1; } else lf = mid + 1; } printf("%d\n", ans); priority_queue< pair<int, int> > PQ; for(int i=1;i<=N;i++) { // cout<<i<<endl; for(int k=0;k<pos[i].size();k++) { PQ.push(make_pair(-i, pos[i][k])); } int V = ans; while(PQ.size() && V) { printf("%d ", PQ.top().second + 1); PQ.pop(); V--; } printf("0\n"); } }

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int k=0;k<pos[i].size();k++) {
      |               ~^~~~~~~~~~~~~~
jobs.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d %d %d", &N, &D, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...