oj.uz

Submission #62689

# Submission time Handle Problem Language Result Execution time Memory
62689 2018-07-29T19:48:03 Z eriksuenderhauf Job Scheduling (CEOI12_jobs) C++11
100 / 100
 393 ms 23008 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define enl printf("\n")
#define ni(n) scanf("%d", &(n))
#define pri(n) printf("%d\n", (n))
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 50;
pii a[MAXN];
vi ans[MAXN / 10];
int n, m, d;
bitset<MAXN> vis;

bool ok(int mi)
{
    int r = 1;
    for (int i = 1; i <= n; i++)
    {
        int tmp = min(m - r + 1, mi);
        for (int j = 0; j < mi && j + r <= m; j++)
        {
            if (a[j + r].fi + d < i)
                return false;
            if (a[j + r].fi > i)
            {
                tmp = j;
                break;
            }
        }
        r += tmp;
    }
    if (r < m)
        return false;
    return true;
}

int main()
{
    ni(n), ni(d), ni(m);
    for (int i = 1; i <= m; i++)
        ni(a[i].fi), a[i].se = i;
    sort(a + 1, a + m + 1);
    int lo = 1, hi = m, ans2 = INF;
    while (lo <= hi)
    {
        int mi = (lo + hi) / 2;
        if (ok(mi))
            hi = mi - 1, ans2 = min(mi, ans2);
        else
            lo = mi + 1;
    }
    int r = 1;
    for (int i = 1; i <= n; i++)
    {
        int tmp = min(m - r + 1, ans2);
        for (int j = 0; j < ans2 && j + r <= m; j++)
        {
            if (a[j + r].fi > i)
            {
                tmp = j;
                break;
            }
            ans[i].pb(a[j + r].se);
        }
        r += tmp;
    }
    pri(ans2);
    for (int i = 1; i <= n; i++, printf("0\n"))
        for (int j: ans[i])
        {
            if (vis[j])
                continue;
            vis[j] = 1;
            printf("%d ", j);
        }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(d), ni(m);
                 ^
jobs.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
jobs.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
jobs.cpp:46:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(a[i].fi), a[i].se = i;
                    ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4560 KB Output is correct
2 Correct 39 ms 4648 KB Output is correct
3 Correct 36 ms 4664 KB Output is correct
4 Correct 62 ms 4664 KB Output is correct
5 Correct 35 ms 4756 KB Output is correct
6 Correct 36 ms 4836 KB Output is correct
7 Correct 35 ms 4908 KB Output is correct
8 Correct 34 ms 4908 KB Output is correct
9 Correct 51 ms 5004 KB Output is correct
10 Correct 53 ms 5008 KB Output is correct
11 Correct 42 ms 5008 KB Output is correct
12 Correct 84 ms 6796 KB Output is correct
13 Correct 149 ms 9260 KB Output is correct
14 Correct 189 ms 11440 KB Output is correct
15 Correct 217 ms 12332 KB Output is correct
16 Correct 316 ms 14424 KB Output is correct
17 Correct 296 ms 18348 KB Output is correct
18 Correct 326 ms 18988 KB Output is correct
19 Correct 393 ms 23008 KB Output is correct
20 Correct 330 ms 23008 KB Output is correct