oj.uz

Submission #739020

# Submission time Handle Problem Language Result Execution time Memory
739020 2023-05-09T18:45:14 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 378 ms 32756 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pi3 = pair<int,pii>;

#define ON(n , k) ( (n) | ( 1 << (k) ))
#define OFF(n ,k) ( (n) & ( ~( 1 << (k))))
#define ISON(n ,k) ( ( (n)>>(k) ) & (1) )
#define F first
#define S second



const int N = 2e5+5;
const int mod = 1e9+7;
const int INF = 1e9+9;
const double PI = 3.1415926536;
int dx[10] = {0,  0, 1, -1, 1,  1, -1, -1, 0};
int dy[10] = {1, -1, 0,  0, 1, -1,  1, -1, 0};
char str[N];


int n, d, m;
vector<pii>v;
vector<vector<int>> v1(N), ans(N);



bool ok(int mid)
{
    for(int i = 0; i < n; i++)
    {
         v1[i].clear();
    }
    int i = 0;
    for(int j = 1; j <= n; j++)
    {

        for(int x = 0; x < mid; x++)
        {
            if(v[i].F > j)break;

            if(v[i].F + d < j)return false;
            v1[j - 1].push_back(v[i].S);
            i++;

            if(i == m)return true;
        }
    }

    return false;
}

void solve()
{
    scanf("%d%d%d", &n, &d, &m);

    for(int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        v.push_back({x, i});
    }

    sort(v.begin(), v.end());


    int l = 0, r = m+2, mid;


    while(l + 1 < r)
    {
        mid = l + (r - l)/2;
        if(ok(mid))
        {
            r = mid;
            ans = v1;
        }
        else
        {
            l = mid;
        }
    }

    printf("%d\n", r);



    for(int j = 0; j < n ; j++)
    {
        for(int x : ans[j])
        {
            printf("%d ", x);
        }
        printf("0\n");
    }


}

int main()
{

    //freopen("", "r", stdin);
    //freopen("", "w", stdout);

    /*
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    */
    int T;
    T = 1 ;
    //scanf("%d" , &T);

    while(T--)
    {
        // init();
        solve();
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d%d%d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12412 KB Output is correct
2 Correct 41 ms 12368 KB Output is correct
3 Correct 34 ms 12408 KB Output is correct
4 Correct 41 ms 12408 KB Output is correct
5 Correct 39 ms 12440 KB Output is correct
6 Correct 37 ms 12404 KB Output is correct
7 Correct 43 ms 12392 KB Output is correct
8 Correct 45 ms 12384 KB Output is correct
9 Correct 59 ms 12396 KB Output is correct
10 Correct 65 ms 12524 KB Output is correct
11 Correct 61 ms 12520 KB Output is correct
12 Correct 106 ms 15340 KB Output is correct
13 Correct 134 ms 18656 KB Output is correct
14 Correct 191 ms 21560 KB Output is correct
15 Correct 206 ms 23256 KB Output is correct
16 Correct 269 ms 26068 KB Output is correct
17 Correct 293 ms 30300 KB Output is correct
18 Correct 343 ms 30616 KB Output is correct
19 Correct 378 ms 32756 KB Output is correct
20 Correct 296 ms 30308 KB Output is correct