oj.uz

Submission #754069

# Submission time Handle Problem Language Result Execution time Memory
754069 2023-06-06T15:30:24 Z textot Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 22296 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000000
#define int long long
struct request{
    int day;
    int id;
};
bool sortbyday(request &r1, request &r2){
    return r1.day<r2.day;
}
int numreqs, numdays, maxdelay; 
request jobreqs[MAXN];
bool works(int nummach){
    int day = 1;
    //check jobreqs by chucks of size nummach and see if any of the jobs are overdue
    while(numreqs>(day-1)*nummach){
        for(int i = 0; i < nummach; i++){
            if(jobreqs[(day-1)*nummach+i].day<day-maxdelay){ //overdue job check
                return false;
            }
        }
        day++;

    }
    return true;
}
signed main(){
    cin>>numdays>>maxdelay>>numreqs;
    int day;
    for(int i = 1; i <= numreqs; i++){
        cin>>day;
        jobreqs[i-1] = {day, i};
    }
    sort(jobreqs, jobreqs+numreqs, sortbyday);
    int lo = 1, hi = MAXN;
    while(lo!=hi){
        int mid = (lo+hi)/2;
        if(works(mid)){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    cout<<lo<<endl;
    int index = 0;
    for(int i = 0; i < numdays; i++){
        for(int j = 0; j < lo; j++){
            if(index < numreqs){
                cout<<jobreqs[index].id<<" ";
                index++;
            }
        }
        cout<<0<<endl;

    }


}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 428 ms 2764 KB Output isn't correct
2 Incorrect 382 ms 2836 KB Output isn't correct
3 Incorrect 419 ms 2908 KB Output isn't correct
4 Incorrect 405 ms 2792 KB Output isn't correct
5 Incorrect 392 ms 2764 KB Output isn't correct
6 Incorrect 394 ms 2924 KB Output isn't correct
7 Incorrect 417 ms 2776 KB Output isn't correct
8 Incorrect 443 ms 3040 KB Output isn't correct
9 Execution timed out 1069 ms 2900 KB Time limit exceeded
10 Execution timed out 1065 ms 2872 KB Time limit exceeded
11 Incorrect 46 ms 2840 KB Output isn't correct
12 Incorrect 83 ms 5348 KB Output isn't correct
13 Incorrect 132 ms 7772 KB Output isn't correct
14 Incorrect 198 ms 10416 KB Output isn't correct
15 Incorrect 202 ms 12796 KB Output isn't correct
16 Incorrect 788 ms 15260 KB Output isn't correct
17 Incorrect 341 ms 17752 KB Output isn't correct
18 Incorrect 565 ms 19804 KB Output isn't correct
19 Execution timed out 1036 ms 22296 KB Time limit exceeded
20 Incorrect 353 ms 17472 KB Output isn't correct