oj.uz

답안 #565652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
565652 2022-05-21T08:13:33 Z PranjalChandra Job Scheduling (CEOI12_jobs) C++14
100 / 100
 325 ms 23752 KB 
#include <bits/stdc++.h>
using namespace std;

#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define ff first
#define ss second
#define endl "\n"
#define pb(x) push_back(x)
#define pp() pop_back()
#define inf MAX_INT
#define dvg(x) cout << #x << " " << x << endl;
#define dvg2(x, y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define dvgv(x)           \
    cout << #x << " { ";  \
    for (auto i : x)      \
    {                     \
        cout << i << " "; \
    }                     \
    cout << "}" << endl;
#define dvgp(x) cout << #x " {" << x.ff << ", " << x.ss << "}" << endl;
int dx[]{-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int const N = 1e5 + 10;
vpii v;
vvi ans;
int n, d, m;

bool ok(int x)
{
    int day = 1, machines = 1;
    ans = vvi(n + 1, vi());
    for (int i = 0; i < m; i++)
    {
        while (day < v[i].ff)
        {
            day++;
            machines = 1;
        }
        if (day - v[i].ff > d)
        {
            return 0;
        }

        ans[day].pb(v[i].ss);
        machines++;
        if (machines > x)
        {
            day++;
            machines = 1;
        }
    }
    return 1;
}
int main()
{
    fastio();

    cin >> n >> d >> m;
    v = vpii(m);
    for (int i = 0; i < m; i++)
    {
        cin >> v[i].ff;
        v[i].ss = i + 1;
    }
    sort(v.begin(), v.end());
    int lo = 0, hi = 1e5 + 12;
    while (lo + 1 < hi)
    {
        int mid = (hi + lo) / 2;
        if (ok(mid))
            hi = mid;
        else
            lo = mid;
    }
    cout << hi << endl;
    ok(hi);
    for (int i = 1; i <= n; i++)
    {
        for (auto j : ans[i])
            cout << j << " ";
        cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2648 KB Output is correct
2 Correct 28 ms 2716 KB Output is correct
3 Correct 29 ms 2728 KB Output is correct
4 Correct 28 ms 2612 KB Output is correct
5 Correct 27 ms 2656 KB Output is correct
6 Correct 28 ms 2636 KB Output is correct
7 Correct 27 ms 2656 KB Output is correct
8 Correct 30 ms 2720 KB Output is correct
9 Correct 56 ms 8664 KB Output is correct
10 Correct 54 ms 9452 KB Output is correct
11 Correct 40 ms 2192 KB Output is correct
12 Correct 74 ms 4240 KB Output is correct
13 Correct 105 ms 6640 KB Output is correct
14 Correct 165 ms 9288 KB Output is correct
15 Correct 173 ms 9672 KB Output is correct
16 Correct 253 ms 12252 KB Output is correct
17 Correct 274 ms 15832 KB Output is correct
18 Correct 274 ms 16588 KB Output is correct
19 Correct 325 ms 23752 KB Output is correct
20 Correct 282 ms 15832 KB Output is correct