oj.uz

Submission #62688

# Submission time Handle Problem Language Result Execution time Memory
62688 2018-07-29T19:45:17 Z eriksuenderhauf Job Scheduling (CEOI12_jobs) C++11
90 / 100
 506 ms 33792 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, vis[MAXN];

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:43: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:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
jobs.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
jobs.cpp:45: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
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5484 KB Output is correct
2 Correct 31 ms 5748 KB Output is correct
3 Correct 64 ms 6108 KB Output is correct
4 Correct 36 ms 6448 KB Output is correct
5 Correct 38 ms 6552 KB Output is correct
6 Correct 38 ms 7068 KB Output is correct
7 Correct 37 ms 7352 KB Output is correct
8 Correct 38 ms 7584 KB Output is correct
9 Correct 77 ms 8012 KB Output is correct
10 Correct 50 ms 8268 KB Output is correct
11 Correct 50 ms 8516 KB Output is correct
12 Correct 89 ms 11096 KB Output is correct
13 Correct 153 ms 14008 KB Output is correct
14 Correct 182 ms 16444 KB Output is correct
15 Correct 233 ms 17764 KB Output is correct
16 Correct 286 ms 20156 KB Output is correct
17 Correct 340 ms 27836 KB Output is correct
18 Correct 459 ms 31820 KB Output is correct
19 Runtime error 506 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Runtime error 344 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.