oj.uz

답안 #71517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71517 2018-08-25T01:07:20 Z MathStudent2002 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 457 ms 16396 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].y = i+1;
    }
    
    sort(job,job+M);
}
 
bool test(long long mech)
{
    int d = 1;
    int num = 0;
    
    for(int i = 0; i < M;i++)
    {
        if(d > (job[i].x+D))
            return false;
            
        while(job[i].x > d)
        {
            d++;
            num = 0;
        }
        num++;
        if(num == mech)
        {
            d++;
            num = 0;
        }
    }
    return true;
}
 
void print(long long mech)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout << mech << endl;
    int d = 1;
    int num = 0;
    
    for(int i = 0; i < M;i++)
    {
        while(job[i].x > d)
        {
            d++;
            num = 0;
            cout << 0 << endl;
        }
        cout << job[i].y << " ";
        num++;
        if(num == mech)
        {
            d++;
            num = 0;
            cout << 0 << endl;
        }
    }
    
    while(d <= N)
    {
        cout << 0 << endl;
        d++;
    }
}
 
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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 1784 KB Output is correct
2 Correct 38 ms 1784 KB Output is correct
3 Correct 43 ms 1984 KB Output is correct
4 Correct 39 ms 1984 KB Output is correct
5 Correct 37 ms 1984 KB Output is correct
6 Correct 43 ms 2024 KB Output is correct
7 Correct 38 ms 2024 KB Output is correct
8 Correct 38 ms 2024 KB Output is correct
9 Correct 177 ms 2296 KB Output is correct
10 Correct 182 ms 2296 KB Output is correct
11 Correct 36 ms 2296 KB Output is correct
12 Correct 72 ms 3484 KB Output is correct
13 Correct 100 ms 4892 KB Output is correct
14 Correct 151 ms 6428 KB Output is correct
15 Correct 184 ms 7852 KB Output is correct
16 Correct 251 ms 9388 KB Output is correct
17 Correct 255 ms 10904 KB Output is correct
18 Correct 291 ms 12332 KB Output is correct
19 Correct 457 ms 16396 KB Output is correct
20 Correct 251 ms 16396 KB Output is correct