oj.uz

답안 #78560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78560 2018-10-06T10:01:07 Z MrTEK Job Scheduling (CEOI12_jobs) C++14
100 / 100
 241 ms 13752 KB 
#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

# 결과 실행 시간 메모리 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