Submission #738989

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
738989	2023-05-09T18:19:12 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	82 / 100	233 ms	13864 KB

jobs

#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;

bool cmp(pii A, pii B)
{
    return A.S < B.S;
}


bool ok(int mid)
{
    int i = 0;
    for(int j = 1; j <= n; j++)
    {
        for(int x = 0; x < mid; x++)
        {
            if(v[i].S > j)break;

            if(v[i].S + d < j)return false;
            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({i, x});
    }

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


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


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

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



    int i = 0;
    for(int j = 1; j <= n ; j++)
    {
        for(int x = 0; x < mid && i < m; x++)
        {
            if(v[i].S > j)break;
            printf("%d ", v[i].F);
            i++;

        }
        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:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d%d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
jobs.cpp:67:25: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     int l = 0, r = m+2, mid;
      |                         ^~~

Subtask #1

82.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1736 KB	Output is correct
2	Correct	21 ms	1784 KB	Output is correct
3	Correct	22 ms	1784 KB	Output is correct
4	Correct	22 ms	1828 KB	Output is correct
5	Correct	20 ms	1736 KB	Output is correct
6	Correct	22 ms	1736 KB	Output is correct
7	Correct	23 ms	1728 KB	Output is correct
8	Correct	24 ms	1804 KB	Output is correct
9	Partially correct	25 ms	1996 KB	Partially correct
10	Partially correct	26 ms	1984 KB	Partially correct
11	Correct	26 ms	1760 KB	Output is correct
12	Correct	51 ms	3224 KB	Output is correct
13	Partially correct	76 ms	4700 KB	Partially correct
14	Correct	111 ms	6320 KB	Output is correct
15	Correct	125 ms	7688 KB	Output is correct
16	Correct	162 ms	9152 KB	Output is correct
17	Partially correct	191 ms	10724 KB	Partially correct
18	Correct	210 ms	12200 KB	Output is correct
19	Partially correct	233 ms	13864 KB	Partially correct
20	Partially correct	188 ms	10708 KB	Partially correct