Submission #521121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521121	2022-01-31T19:13:18 Z	it111	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	355 ms	17320 KB

jobs

#include <bits/stdc++.h>

using namespace std;
struct uzsakymas{
    int diena;
    int eilesNr;
    int priimtas;
};
uzsakymas uzsakymai[1000005];
int n,d,m;
bool rikiavimas (uzsakymas a, uzsakymas b){
    return a.diena<b.diena;
}
bool tinka(int dirba){
    int dabarDiena = 1;
    for(int i = 0; i<m; i++){
        for(int j = 0; j<dirba; j++){
            if(dabarDiena-uzsakymai[i].diena<0){
                break;
            }
            if(dabarDiena-uzsakymai[i].diena>d){
                return false;
            }
            uzsakymai[i].priimtas = dabarDiena;
            i++;
            if(i==m){
                return true;
            }
        }
        i--;
        dabarDiena++;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> d >> m;
    for(int i = 1; i<=m; i++){
        int a; cin >> a;
        uzsakymai[i-1].diena = a;
        uzsakymai[i-1].eilesNr = i;
    }
    sort(uzsakymai,uzsakymai+m,rikiavimas);
    int k = 0; int d = m;
    int ats = INT_MAX;
    while(k<d){
        int v = (k+d+1)/2;
        if(tinka(v)){
            ats = min(ats,v);
            d = v-1;
        } else{
            k = v;
        }
    }
    cout << ats << endl;
    int nr = 0;
    for(int i = 1; i<=n; i++){
        while(uzsakymai[nr].priimtas==i and nr<m){
            cout << uzsakymai[nr].eilesNr << " ";
            nr++;
        }
        cout << 0 << endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1996 KB	Output is correct
2	Correct	29 ms	2092 KB	Output is correct
3	Correct	28 ms	2000 KB	Output is correct
4	Correct	28 ms	2048 KB	Output is correct
5	Correct	29 ms	1988 KB	Output is correct
6	Correct	32 ms	1996 KB	Output is correct
7	Correct	28 ms	1996 KB	Output is correct
8	Correct	28 ms	2076 KB	Output is correct
9	Correct	129 ms	2244 KB	Output is correct
10	Correct	129 ms	2268 KB	Output is correct
11	Correct	23 ms	1988 KB	Output is correct
12	Correct	47 ms	3908 KB	Output is correct
13	Correct	68 ms	5744 KB	Output is correct
14	Correct	107 ms	7704 KB	Output is correct
15	Correct	113 ms	9520 KB	Output is correct
16	Correct	160 ms	11444 KB	Output is correct
17	Correct	183 ms	13260 KB	Output is correct
18	Correct	196 ms	15220 KB	Output is correct
19	Correct	355 ms	17320 KB	Output is correct
20	Correct	185 ms	13236 KB	Output is correct