oj.uz

Submission #71485

# Submission time Handle Problem Language Result Execution time Memory
71485 2018-08-24T22:26:27 Z MathStudent2002 Job Scheduling (CEOI12_jobs) C++14
55 / 100
 707 ms 14028 KB 
//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)
{
    if(mech < (M+N)/N)
    {
        if(mech*N < M)
            return false;
    }
    
    for(int i = 0; i < M;i++)
    {
        if(job[i].x < ((i/mech)+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());
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 1784 KB Output isn't correct
2 Incorrect 65 ms 1908 KB Output isn't correct
3 Incorrect 64 ms 1908 KB Output isn't correct
4 Incorrect 57 ms 1908 KB Output isn't correct
5 Incorrect 74 ms 1984 KB Output isn't correct
6 Incorrect 62 ms 1996 KB Output isn't correct
7 Incorrect 63 ms 1996 KB Output isn't correct
8 Incorrect 61 ms 2012 KB Output isn't correct
9 Correct 221 ms 2152 KB Output is correct
10 Correct 198 ms 2240 KB Output is correct
11 Correct 57 ms 2240 KB Output is correct
12 Correct 106 ms 3468 KB Output is correct
13 Correct 171 ms 4904 KB Output is correct
14 Correct 228 ms 6508 KB Output is correct
15 Incorrect 297 ms 7908 KB Output isn't correct
16 Correct 327 ms 9384 KB Output is correct
17 Correct 440 ms 10792 KB Output is correct
18 Correct 556 ms 12316 KB Output is correct
19 Correct 707 ms 14028 KB Output is correct
20 Correct 442 ms 14028 KB Output is correct