Submission #471921

#	Time	Username	Problem	Language	Result	Execution time	Memory
471921		DDTerziev04	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	327 ms	17084 KiB

jobs

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXM=1e6, MAXR=1e6;

pair<int, int> a[MAXM];

bool CanProcess(int n, int d, int m, int cnt)
{
   for(int i=0; i<n; i++)
   {
      int l=min(m-1, i*cnt), r=min(m-1, (i+1)*cnt-1);
      if(i-a[l].first+1>d)
      {
         return false;
      }

      if(r==m-1)
      {
         break;
      }
   }

   return true;
}

void PrintAns(int n, int d, int m, int cnt)
{
   for(int i=0; i<n; i++)
   {
      int l=min(m-1, i*cnt), r=min(m-1, (i+1)*cnt-1);
      if(i*cnt<m)
      {
         for(int j=l; j<=r; j++)
         {
            cout << a[j].second+1 << " ";
         }
      }

      cout << "0\n";
   }

   return;
}


int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int n, d, m;
   cin >> n >> d >> m;

   for(int i=0; i<m; i++)
   {
      cin >> a[i].first;

      a[i].second=i;
   }
   sort(a, a+m);


   int l=0, r=MAXR, ans;
   while(l<=r)
   {
      int mid=l+(r-l)/2;
      if(CanProcess(n, d, m, mid))
      {
         ans=mid;
         r=mid-1;
      }
      else
      {
         l=mid+1;
      }
   }

   cout << ans << "\n";

   PrintAns(n, d, m, ans);

   return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:82:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |    PrintAns(n, d, m, ans);
      |    ~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 55 / 100