Submission #48578

#	Time	Username	Problem	Language	Result	Execution time	Memory
48578		doowey	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	178 ms	15408 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>R[N];
int has_done[N];

bool can(int k){
  for(int i = 0;i < N; i ++ )
    has_done[i] = 0;
  int tt = 0;
  for(int i = 1;i <= d;i ++ )
    tt += len(R[i]);
  if(tt >= (d + 1) * k)
    return false;
  int p = 1;
  for(int i = d + 1;i <= n;i ++ ){
    tt -= len(R[p]);
    p++;
    if(tt >= (d + 1) * k)
      return false;
  }
  return true;
}

void output_solution(int answer){
  cout << answer << "\n";
  for(int j = 0;j < N;j ++ )
    has_done[j] = 0;
  int p = 1;
  int tt;
  for(int i = 1;i <= n;i ++ ){
    tt = answer;
    while(p <= i and tt > 0){
      if(len(R[p]) == has_done[p]){
        p++;
        continue;
      }
      cout << R[p][has_done[p]] << " ";   
      has_done[p]++;
      tt--;
    }
    cout << "0\n";
  }
}

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

• Subtask 1: 0 / 100