Submission #48621

#	Time	Username	Problem	Language	Result	Execution time	Memory
48621		doowey	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	293 ms	15760 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
	
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TEST freopen("in.txt","r",stdin);
#define ab(a) ((a < 0) ? (-(a)) : (a))
#define len(x) ((int)(x).size())
#define ones(x) __builtin_popcount((x))
#define all(x) x.begin(), x.end()

const int N = (int)1e5 + 999;
int n,d;
vector<int>J[N];
int rem[N];

bool can(int k){
  for(int i = 1;i <= n;i ++)
    rem[i] = J[i].size();
  int p = 1;
  int tt = 0;
  int kk;
  for(int i = 1;i <= n;i ++){
    kk = k;
    if(i - p > d)
      return false;
    while(kk > 0 && p <= i){
      if(rem[p] == 0){
        p++;
        continue;
      }
      kk--;
      rem[p]--;
    }
  }
  return true;
}

void output_solution(int x){
  cout << x << "\n";
  int p = 1;
  int tt;
  for(int i = 1;i <= n;i ++ ){
    tt = x;
    while(p <= i and tt > 0){
      if(J[p].empty()){
        p++;
        continue;
      }
      cout << J[p].back() << " ";
      tt--;
      J[p].pop_back();
    }
    cout << "0\n";
  }
}

int main(){
  fastIO;
  int m;
  cin >> n >> d >> m;
  int x;
  for(int i = 1 ;i <= m;i ++){
    cin >> x;
    J[x].push_back(i);
  }
  int lf = 0,rf = m + 1;
  int md;
  while(rf-lf > 1){
    md = (lf + rf) / 2;
    if(can(md))
      rf = md;
    else
      lf = md;
  }
  output_solution(rf);
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool can(int)':
jobs.cpp:28:7: warning: unused variable 'tt' [-Wunused-variable]
   int tt = 0;
       ^~

• Subtask 1: 60 / 100