Submission #471924

#	Time	Username	Problem	Language	Result	Execution time	Memory
471924		DDTerziev04	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	282 ms	13660 KiB

jobs

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

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

pair<int, int> a[MAXM];

int GetEnd(int m, int cnt, int d)
{
   int l=0, r=m-1, ans=-1;
   while(l<=r)
   {
      int mid=l+(r-l)/2;
      if(a[mid].first<=d)
      {
         ans=mid;
         l=mid+1;
      }
      else
      {
         r=mid-1;
      }
   }

   return ans;
}

bool CanProcess(int n, int d, int m, int cnt)
{
   int prev=-1;
   for(int i=0; i<n; i++)
   {
      int l=prev+1, r=min(prev+cnt, GetEnd(m, cnt, i+1));
      if(r<l)
      {
         continue;
      }

      if(i-a[l].first+1>d)
      {
         return false;
      }

      if(r==m-1)
      {
         return true;
      }

      prev=r;
   }

   return false;
}

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

         prev=r;
      }

      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;
}
/*
8 2 12
1 1 2 2 2 3 3 4 4 5 6 6
*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100