Submission #738987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
738987	2023-05-09T18:15:38 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	82 / 100	247 ms	13832 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 j = 1, i = 0;
    while(j <= n)
    {
        int s = i;
        for(i; i < s + mid && i < m; i++)
        {

            printf("%d ", v[i].F);

        }
        j++;

        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:89:13: warning: statement has no effect [-Wunused-value]
   89 |         for(i; i < s + mid && i < m; i++)
      |             ^
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:89:22: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |         for(i; i < s + mid && i < m; i++)
      |                    ~~^~~~~

Subtask #1

82.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1724 KB	Output is correct
2	Correct	23 ms	1836 KB	Output is correct
3	Correct	21 ms	1736 KB	Output is correct
4	Correct	21 ms	1744 KB	Output is correct
5	Correct	21 ms	1736 KB	Output is correct
6	Correct	20 ms	1816 KB	Output is correct
7	Correct	23 ms	1772 KB	Output is correct
8	Correct	21 ms	1744 KB	Output is correct
9	Partially correct	27 ms	1972 KB	Partially correct
10	Partially correct	30 ms	1976 KB	Partially correct
11	Correct	26 ms	1744 KB	Output is correct
12	Correct	55 ms	3188 KB	Output is correct
13	Partially correct	81 ms	4696 KB	Partially correct
14	Correct	115 ms	6344 KB	Output is correct
15	Correct	129 ms	7620 KB	Output is correct
16	Correct	170 ms	9252 KB	Output is correct
17	Partially correct	233 ms	10740 KB	Partially correct
18	Correct	217 ms	12200 KB	Output is correct
19	Partially correct	247 ms	13832 KB	Partially correct
20	Partially correct	196 ms	10652 KB	Partially correct