Submission #471924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471924	2021-09-11T18:14:30 Z	DDTerziev04	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	282 ms	13660 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1604 KB	Output is correct
2	Correct	21 ms	1612 KB	Output is correct
3	Correct	20 ms	1656 KB	Output is correct
4	Correct	20 ms	1600 KB	Output is correct
5	Correct	25 ms	1732 KB	Output is correct
6	Correct	20 ms	1624 KB	Output is correct
7	Correct	20 ms	1652 KB	Output is correct
8	Correct	20 ms	1608 KB	Output is correct
9	Correct	34 ms	1836 KB	Output is correct
10	Correct	34 ms	1860 KB	Output is correct
11	Correct	32 ms	1644 KB	Output is correct
12	Correct	60 ms	3156 KB	Output is correct
13	Correct	91 ms	4572 KB	Output is correct
14	Correct	141 ms	6052 KB	Output is correct
15	Correct	151 ms	7744 KB	Output is correct
16	Correct	203 ms	9028 KB	Output is correct
17	Correct	242 ms	10564 KB	Output is correct
18	Correct	252 ms	12108 KB	Output is correct
19	Correct	282 ms	13660 KB	Output is correct
20	Correct	238 ms	10564 KB	Output is correct