Submission #78560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78560	2018-10-06T10:01:07 Z	MrTEK	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	241 ms	13752 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	4080 KB	Output is correct
2	Correct	28 ms	4212 KB	Output is correct
3	Correct	25 ms	4212 KB	Output is correct
4	Correct	26 ms	4212 KB	Output is correct
5	Correct	28 ms	4212 KB	Output is correct
6	Correct	27 ms	4212 KB	Output is correct
7	Correct	26 ms	4240 KB	Output is correct
8	Correct	40 ms	4292 KB	Output is correct
9	Correct	37 ms	4380 KB	Output is correct
10	Correct	33 ms	4380 KB	Output is correct
11	Correct	29 ms	4380 KB	Output is correct
12	Correct	64 ms	5348 KB	Output is correct
13	Correct	73 ms	7084 KB	Output is correct
14	Correct	119 ms	8400 KB	Output is correct
15	Correct	105 ms	9256 KB	Output is correct
16	Correct	168 ms	11048 KB	Output is correct
17	Correct	200 ms	13004 KB	Output is correct
18	Correct	241 ms	13004 KB	Output is correct
19	Correct	227 ms	13752 KB	Output is correct
20	Correct	208 ms	13752 KB	Output is correct