oj.uz

Submission #333573

# Submission time Handle Problem Language Result Execution time Memory
333573 2020-12-07T05:11:11 Z siddarthm Job Scheduling (CEOI12_jobs) C++11
55 / 100
 265 ms 2796 KB 
#include <iostream>
#include <algorithm>
using namespace std;

pair<int,int> orders[100000];
int n,d,m;

bool works(int x)
{
    int point = 0;
    //cout << x << endl;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<x; j++)
        {
            if(orders[point].first>i)
                break;
            if(i>(orders[point].first+d))
                return false;
            //cout << point << " ";
            point++;
            if(point==m)
                break;
        }
        //cout << endl;
        if(point==m)
            break;
    }
    if(point<m)
        return false;
    return true;
}

int main(){
    cin >> n >> d >> m;
    for(int i=0; i<m; i++)
    {
        cin >> orders[i].first;
        orders[i].second = i+1;
    }
    sort(orders, orders+m);
    int a = 1;
    int b = m;
    while(a!=b)
    {
        int mid = (a+b)/2;
        if(works(mid))
            b = mid;
        else
            a = mid+1;
        //cout << endl;
    }
    cout << a << endl;
    int point = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<a; j++)
        {
            if(point==m)
                break;
            if(orders[point].first>i)
                break;
            cout << orders[point].second << " ";
            point++;
        }
        cout << 0 << endl;
    }
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2028 KB Output is correct
2 Correct 59 ms 2044 KB Output is correct
3 Correct 59 ms 2028 KB Output is correct
4 Correct 59 ms 2028 KB Output is correct
5 Correct 67 ms 2028 KB Output is correct
6 Correct 58 ms 2028 KB Output is correct
7 Correct 58 ms 2028 KB Output is correct
8 Correct 59 ms 2012 KB Output is correct
9 Correct 264 ms 2156 KB Output is correct
10 Correct 265 ms 2216 KB Output is correct
11 Correct 53 ms 2028 KB Output is correct
12 Runtime error 26 ms 2656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 40 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 29 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 25 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 28 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 28 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 26 ms 2796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 25 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 28 ms 2796 KB Execution killed with signal 11 (could be triggered by violating memory limits)