Submission #454918

#	Time	Username	Problem	Language	Result	Execution time	Memory
454918		geometryisop	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	1061 ms	27212 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll n,d,m;
  cin>>n>>d>>m;
  ll a[m];
  vector< vector<int>> vii;
  map <ll,ll> mp;
  vii.assign(n+5,vector<int>());
  for (int i=0;i<m;i++)
  {
      cin>>a[i];
     // cout<<a[i]<<endl;
      vii[a[i]].push_back(i+1);
      mp[a[i]]++;
  }
 // cout<<vii[1][0];
  //cout<<" "<<vii[1][1]<<endl;
  ll l=0;
  ll r=1000000;
  ll ans=r;
  while(l<=r)
  {
      ll mid=(l+r)/2;
      //check if works for mid
      ll machines=mid;
      ll deadline=n-d;
      ll up=mid;
      bool flag=true;
      for (int i=deadline;i>=1;i--)
      {
          if (up-mp[i]>=0)
          {
              up-=mp[i];
              up+=mid;
          }
          else
          {
              flag=false;
              break;
          }
      }
      if (flag)
      {
          ans=min(ans,mid);
          r=mid-1;
      }
      else
        l=mid+1;

  }
  vector <int> v;
  cout<<ans<<endl;  ll cnt=0;
  for (int i=1;i<=n;i++)
  {
      if (i>n-d)
      {
          cout<<0<<endl;
      }
      else
      {
          bool allakse=false;

          for (int j=0;j<vii[i].size();j++)
          {
            cout<<vii[i][j]<<" ";
              cnt++;
              if (cnt==ans)
              {
                  cnt=0;
                  cout<<0<<endl;
                  allakse=true;//allakse i mera;
              }
          }
          if (!allakse)
          {
              cout<<0<<endl;
          }
      }
  }
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:28:10: warning: unused variable 'machines' [-Wunused-variable]
   28 |       ll machines=mid;
      |          ^~~~~~~~
jobs.cpp:66:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |           for (int j=0;j<vii[i].size();j++)
      |                        ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100