oj.uz

답안 #499609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499609 2021-12-29T02:45:36 Z hades42 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 346 ms 24336 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef tuple<ll, ll, ll> tp;
typedef pair<ll, ll> pr;

const ll MOD = 1000000007;
const ll INF = 1e18;

template <typename T> void print(const T &t) {
  std::copy(t.cbegin(), t.cend(),
            std::ostream_iterator<typename T::value_type>(std::cout, " "));
  cout << endl;
}

template <typename T> void print2d(const T &t) {
  std::for_each(t.cbegin(), t.cend(), print<typename T::value_type>);
}

void setIO(string s) { // the argument is the filename without the extension
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
ll n, d, m; 
vector<pr> arr;
bool check(ll machine){
    ll i = 0; 
    ll wait = 0;
    ll currDay = 1;
    ll count = 0;
    while(i < m){
        while(i < m && count < machine){
            ll delay = max((ll)0, currDay - arr[i].first);
            wait = max(delay, wait);
            count++;
            i++;
        }
        currDay++;
        count = 0;
    }
    return wait > d;
}

bool works(ll robots)
{
	ll endT[robots] = {0};
	ll maxD = 0;

	for (ll i = 0, cur = 0; i < m; i++, cur++) {
		if (cur == robots)
			cur = 0;
		// if our end time for this job is > than our start time for this job
		// there will be delay
		if (endT[cur] + 1 > arr[i].first) {
			endT[cur]++;
			maxD = max(maxD, endT[cur] - arr[i].first);
		}
		else
			endT[cur] = arr[i].first;
	}
	return maxD > d;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> d >> m;
    arr.resize(m);
    for(ll i = 0; i < m; i++){
        ll num; cin >> num;
        arr[i] = {num, i + 1};
    }
    sort(arr.begin(), arr.end());
    //for(ll i = 0; i < n; i++){
        //cout << arr[i].first << " " << arr[i].second << endl;
    //}
    ll left = 1;
    ll right = m;
    while(left < right){
        ll mid = left + (right - left)/2;
        if(works(mid)){
            left = mid + 1; 
        } else{
            right = mid;
        }
    }
    ll need = left;
    ll curr = 0;
    ll count = 0;
    cout << need << endl;
    for(ll i = 0; i < n; i++){
        while(count < need && curr < m){
            cout << arr[curr].second << " ";
            curr++;
            count++;
        }
        count = 0;
        cout << 0 << endl;
    }
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:23:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2764 KB Output is correct
2 Correct 34 ms 2884 KB Output is correct
3 Correct 28 ms 2888 KB Output is correct
4 Correct 28 ms 2876 KB Output is correct
5 Correct 32 ms 2908 KB Output is correct
6 Correct 28 ms 2764 KB Output is correct
7 Correct 28 ms 2768 KB Output is correct
8 Correct 28 ms 2872 KB Output is correct
9 Correct 142 ms 3024 KB Output is correct
10 Correct 144 ms 2932 KB Output is correct
11 Correct 24 ms 2776 KB Output is correct
12 Correct 51 ms 5496 KB Output is correct
13 Correct 73 ms 8104 KB Output is correct
14 Correct 110 ms 10804 KB Output is correct
15 Correct 124 ms 13520 KB Output is correct
16 Correct 170 ms 16116 KB Output is correct
17 Correct 187 ms 18832 KB Output is correct
18 Correct 207 ms 21404 KB Output is correct
19 Correct 346 ms 24336 KB Output is correct
20 Correct 188 ms 18820 KB Output is correct