Submission #71484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71484	2018-08-24T22:15:09 Z	MathStudent2002	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	455 ms	16324 KB

jobs

//wait darn

#include<bits/stdc++.h>

using namespace std;

#define MAXM 1000005
#define x first 
#define y second

int M, N, D;

pair<int,int> job[MAXM];

void read()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cin >> N >> D >> M;
    for(int i = 0; i < M; i++)
    {
        cin >> job[i].x;
        job[i].x += D;
        job[i].y = i+1;
    }
    
    sort(job,job+M);
}

bool test(long long mech)
{
    long long cur = 0;
    int d = 0;
    
    if(mech < (M+N)/N)
    {
        if(mech*N < M)
            return false;
    }
    
    for(int i = 0; i < M;i++)
    {
        if(job[i].x < ((i/D)+1))
            return false;
    }
    return true;
}

void print(long long mech)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout << mech << endl;
    int d = 0;
    for(int i = 0; i < M;i++)
    {
        cout << job[i].y << " ";
        
        if((i+1)%mech == 0)
        {
            cout << 0 << endl;
            d++;
        }
    }
    
    for(; d < N; d++)
        cout << 0 << endl;
}

int solve()
{
    int lo = 1, hi = M, mi;
    while(hi - lo > 1)
    {
        mi = (lo+hi)/2;
        if(test(mi))
            hi = mi;
        else
            lo = mi;
    }
    if(test(lo))
        return lo;
    return hi;
}

int main()
{
    read();
    print(solve());
}

Compilation message

jobs.cpp: In function 'bool test(long long int)':
jobs.cpp:32:15: warning: unused variable 'cur' [-Wunused-variable]
     long long cur = 0;
               ^~~
jobs.cpp:33:9: warning: unused variable 'd' [-Wunused-variable]
     int d = 0;
         ^

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	41 ms	1784 KB	Output isn't correct
2	Incorrect	53 ms	1908 KB	Output isn't correct
3	Incorrect	42 ms	1908 KB	Output isn't correct
4	Incorrect	39 ms	1908 KB	Output isn't correct
5	Incorrect	37 ms	1908 KB	Output isn't correct
6	Incorrect	37 ms	2000 KB	Output isn't correct
7	Incorrect	64 ms	2072 KB	Output isn't correct
8	Incorrect	43 ms	2072 KB	Output isn't correct
9	Incorrect	178 ms	2252 KB	Output isn't correct
10	Incorrect	215 ms	2252 KB	Output isn't correct
11	Incorrect	34 ms	2252 KB	Output isn't correct
12	Incorrect	70 ms	3460 KB	Output isn't correct
13	Incorrect	104 ms	4884 KB	Output isn't correct
14	Correct	166 ms	6392 KB	Output is correct
15	Incorrect	167 ms	7920 KB	Output isn't correct
16	Incorrect	230 ms	9388 KB	Output isn't correct
17	Incorrect	307 ms	10796 KB	Output isn't correct
18	Incorrect	299 ms	12272 KB	Output isn't correct
19	Incorrect	455 ms	16324 KB	Output isn't correct
20	Incorrect	314 ms	16324 KB	Output isn't correct