Submission #738992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
738992	2023-05-09T18:20:53 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	82 / 100	266 ms	13868 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].F > j)break;

            if(v[i].F + 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({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;
        }
        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].F > j)break;
            printf("%d ", v[i].S);
            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	24 ms	1812 KB	Output is correct
2	Correct	24 ms	1732 KB	Output is correct
3	Correct	21 ms	1812 KB	Output is correct
4	Correct	21 ms	1744 KB	Output is correct
5	Correct	20 ms	1736 KB	Output is correct
6	Correct	20 ms	1808 KB	Output is correct
7	Correct	22 ms	1736 KB	Output is correct
8	Correct	20 ms	1784 KB	Output is correct
9	Partially correct	32 ms	1992 KB	Partially correct
10	Partially correct	31 ms	1984 KB	Partially correct
11	Correct	31 ms	1864 KB	Output is correct
12	Correct	64 ms	3208 KB	Output is correct
13	Partially correct	102 ms	4720 KB	Partially correct
14	Correct	137 ms	6248 KB	Output is correct
15	Correct	147 ms	7728 KB	Output is correct
16	Correct	176 ms	9156 KB	Output is correct
17	Partially correct	206 ms	10660 KB	Partially correct
18	Correct	236 ms	12196 KB	Output is correct
19	Partially correct	266 ms	13868 KB	Partially correct
20	Partially correct	206 ms	10660 KB	Partially correct