Submission #706267

#TimeUsernameProblemLanguageResultExecution timeMemory
706267ToroTNJob Scheduling (CEOI12_jobs)C++14
30 / 100
798 ms16064 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back int n,d,m,job[100005],num,st,md,ed,type,flag; priority_queue<int> pq; priority_queue<pair<int,int> >pq2; vector<int> v[100005]; int main() { scanf("%d%d%d",&n,&d,&m); for(int i=1;i<=m;i++) { scanf("%d",&num),++job[num]; v[num].pb(i); } st=1; ed=1000000; while(ed>=st) { md=(st+ed)/2; //printf("%d %d %d\n",st,md,ed); type=0; while(!pq.empty())pq.pop(); for(int i=1;i<=n;i++) { for(int j=0;j<job[i];j++)pq.push(-i); if(pq.size()!=0) { if(i>=-pq.top()+d) { type=-1; } flag=min((int)pq.size(),md); for(int j=1;j<=flag;j++)pq.pop(); } } if(pq.size()>0)type=-1; if(type==0) { ed=md-1; }else { st=md+1; } } while(!pq.empty()) { pq.pop(); } printf("%d\n",st); for(int i=1;i<=n;i++) { for(int j=0;j<v[i].size();j++) { pq2.push({-i,v[i][j]}); } if(pq2.size()!=0) { flag=min((int)pq2.size(),st); for(int j=1;j<=flag;j++) { printf("%d ",pq2.top().Y); pq2.pop(); } } printf("0\n"); } }

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
jobs.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d%d",&n,&d,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d",&num),++job[num];
      |         ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...