Submission #78560

#	Time	Username	Problem	Language	Result	Execution time	Memory
78560		MrTEK	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	241 ms	13752 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

vector <int> v[N];

int n,d,m;

bool check(int mach) {
  queue <int> Q;
  for (int i = 1 ; i <= n ; i++) {
    int temp = mach;
    while(Q.empty() == false && temp) {
      Q.pop();
      temp--;
    }
    for (int j = 1; j <= max(0,(int)v[i].size() - temp) ; j++)
      Q.push(i);
    if (Q.empty() == false && i+ 1 - Q.front() > d)
      return false;
  }
  return Q.empty() == true;
}

void write(int mach) {
  queue <int> Q;
  for (int i = 1 ; i <= n ; i++) {
    int temp = mach;
    while(Q.empty() == false && temp) {
      cout << Q.front() << " ";
      Q.pop();
      temp--;
    }
    int t = 0;
    for (int j = 0; j < max(0,(int)v[i].size() - temp) ; j++) {
      Q.push(v[i][j]);
      t++;
    }
    for ( ; t < v[i].size() ; t++)
      cout << v[i][t] << " ";
    cout << "0\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> d >> m;
  for (int i = 1 ; i <= m ; i++) {
    int a;
    cin >> a;
    v[a].push_back(i);
  }
  int l = 1,r = m;
  while(l < r) {
    int mid = (l + r - 1) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l << endl;
  write(l);
}

Compilation message (stderr)

jobs.cpp: In function 'void write(int)':
jobs.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( ; t < v[i].size() ; t++)
             ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100