Submission #304880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
304880	2020-09-22T05:44:16 Z	waterfall	Job Scheduling (CEOI12_jobs)	C++11	55 / 100	913 ms	26104 KB

jobs

#include<bits/stdc++.h>
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

string s = "";

bool works(int num, int m, pair<int, int> requests[], int delay)
{
    int arr[num+1];
    memset(arr, 0, sizeof(arr));

    for(int i = 0; i < m; i++)
    {
        int machineNum = i % num;
        int day = max(requests[i].first, arr[machineNum] + 1);
        if(abs(requests[i].first - day) > delay)
        {
            return false;
        }

        arr[machineNum]++;
    }

    return true;

}

int32_t main()
{
    int n, d, m;
    cin >> n >> d >> m;

    pair<int, int> requests[m];
    for(int i = 0; i < m; i++)
    {
        int temp;
        cin >> temp;
        requests[i] = make_pair(temp, (i+1));
    }

    sort(requests, requests + m);

    int lower = 1;
    int upper = m;
    while(lower != upper)
    {
        int mid = (lower + upper ) / 2;
        if(works(mid, m, requests, d))
        {
            upper = mid;
        }
        else
        {
            lower = mid + 1;
        }
    }

    cout << lower << endl;

    int arr[lower + 1];
    memset(arr, 0, sizeof(arr));

    int curDay = 1;
    for(int i = 0; i < m; i++)
    {
        int machineNum = i % lower;
        int day = max(requests[i].first, arr[machineNum] + 1);
        arr[machineNum]++;

        if(day == curDay)
        {
            cout << requests[i].second << " ";
        }
        else if(day == curDay + 1)
        {
            cout << "0" << endl;
            cout << requests[i].second << " ";
            curDay = day;
        }
        else
        {
            for(int i = day; i < curDay - 1; i++)
            {
                cout << "0" << endl;
            }
            cout << requests[i].second << " ";
            curDay = day;
        }
    }

    cout << "0" << endl;
    if(curDay != n)
    {
        for(int i = curDay; i < n; i++)
        {
            cout << "0" << endl;
        }
    }
    return 0;
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	79 ms	3192 KB	Output isn't correct
2	Incorrect	78 ms	3192 KB	Output isn't correct
3	Incorrect	79 ms	3192 KB	Output isn't correct
4	Incorrect	81 ms	3224 KB	Output isn't correct
5	Incorrect	79 ms	3192 KB	Output isn't correct
6	Incorrect	80 ms	3220 KB	Output isn't correct
7	Incorrect	79 ms	3192 KB	Output isn't correct
8	Incorrect	83 ms	3192 KB	Output isn't correct
9	Correct	278 ms	3320 KB	Output is correct
10	Correct	277 ms	3320 KB	Output is correct
11	Correct	75 ms	3320 KB	Output is correct
12	Correct	155 ms	6264 KB	Output is correct
13	Correct	226 ms	8824 KB	Output is correct
14	Correct	353 ms	12280 KB	Output is correct
15	Incorrect	374 ms	14872 KB	Output isn't correct
16	Correct	513 ms	17596 KB	Output is correct
17	Correct	599 ms	20344 KB	Output is correct
18	Correct	632 ms	22904 KB	Output is correct
19	Correct	913 ms	26104 KB	Output is correct
20	Correct	602 ms	20728 KB	Output is correct