oj.uz

답안 #751843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751843 2023-06-01T15:34:40 Z ndh990 Job Scheduling (CEOI12_jobs) C++11
80 / 100
 581 ms 47036 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pairs;
using vi = vector<ll>;
const ll MOD = 1e9+7;
#define mp make_pair
 ll n,d,m;
pair<bool, vector<vi>> isFeasible(const vector<pairs> &jobs, int machineCount) {
        vector<vi> schedule(n);
        ll reqNum = 0;
for (ll day = 1; day <= n; day++) {
    for (ll j = 0; j < machineCount; j++) {
            if(jobs[reqNum].first>day)
        {
            break;
        }
        if(jobs[reqNum].first+d>=day)
        {
            schedule[day-1].push_back(jobs[reqNum++].second);
        }
        else return mp(false, schedule);
        if (reqNum == m) return mp(true, schedule);
    }
}
return mp(false, schedule);
}
int main()
{
    cin >> n >> d >> m;
    vector <pairs> jobs(m);
    for(int i=0;i<m;i++)
    {
        cin >> jobs[i].first;
        jobs[i].second=i+1;
    }
    sort(jobs.begin(),jobs.end());
    int l =1;
    int r =m;
    vector<vi> result;
    while (l < r) {
		int machineNum = l+(r - l) / 2;
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
		if (curResult.first) {
			r = machineNum;
			result = curResult.second;
		}
		else
			l = machineNum + 1;
    }
    cout << l << "\n";
	for (int i = 0; i < n; i++) {
		for (auto &idx : result[i]) cout << idx << " ";
		cout << 0 << "\n";
	}







}

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 5528 KB Output is correct
2 Correct 44 ms 5532 KB Output is correct
3 Correct 47 ms 5516 KB Output is correct
4 Correct 45 ms 5528 KB Output is correct
5 Correct 43 ms 5524 KB Output is correct
6 Correct 46 ms 5520 KB Output is correct
7 Correct 45 ms 5540 KB Output is correct
8 Correct 49 ms 5532 KB Output is correct
9 Correct 89 ms 12088 KB Output is correct
10 Correct 92 ms 12204 KB Output is correct
11 Correct 55 ms 5308 KB Output is correct
12 Correct 121 ms 9604 KB Output is correct
13 Correct 185 ms 15208 KB Output is correct
14 Correct 324 ms 20948 KB Output is correct
15 Correct 333 ms 22684 KB Output is correct
16 Correct 401 ms 28708 KB Output is correct
17 Runtime error 503 ms 36696 KB Memory limit exceeded
18 Runtime error 486 ms 41212 KB Memory limit exceeded
19 Runtime error 581 ms 47036 KB Memory limit exceeded
20 Runtime error 479 ms 36640 KB Memory limit exceeded