Submission #71483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71483	2018-08-24T22:13:57 Z	MathStudent2002	Job Scheduling (CEOI12_jobs)	C++14	5 / 100	474 ms	33792 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++;
        }
    }
    
    if(M%mech != 0)
        cout << 0 << endl;
    
    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	40 ms	2040 KB	Output isn't correct
2	Incorrect	41 ms	2460 KB	Output isn't correct
3	Incorrect	37 ms	2752 KB	Output isn't correct
4	Incorrect	41 ms	3212 KB	Output isn't correct
5	Incorrect	41 ms	3632 KB	Output isn't correct
6	Incorrect	41 ms	3924 KB	Output isn't correct
7	Incorrect	44 ms	4180 KB	Output isn't correct
8	Incorrect	48 ms	4516 KB	Output isn't correct
9	Incorrect	191 ms	4964 KB	Output isn't correct
10	Incorrect	190 ms	5196 KB	Output isn't correct
11	Incorrect	42 ms	5316 KB	Output isn't correct
12	Incorrect	67 ms	7620 KB	Output isn't correct
13	Incorrect	119 ms	10172 KB	Output isn't correct
14	Correct	191 ms	13656 KB	Output is correct
15	Incorrect	188 ms	16960 KB	Output isn't correct
16	Incorrect	235 ms	21524 KB	Output isn't correct
17	Incorrect	303 ms	26200 KB	Output isn't correct
18	Incorrect	288 ms	30800 KB	Output isn't correct
19	Runtime error	474 ms	33792 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20	Runtime error	320 ms	33792 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.