Submission #465151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465151	2021-08-15T09:12:03 Z	tphuc2908	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	391 ms	13780 KB

jobs

#include<bits/stdc++.h>

using namespace std;
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
typedef long long ll;
typedef vector<int> vi;
const int N = 1e6 + 5;
const int mod = 1e9+7;
const int inf = 1e9 + 5;

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("angry.in", "r", stdin);
//    freopen("angry.out", "w", stdout);
}

int n, d, m;
pair<int,int> a[N];

void inp(){
    cin >> n >> d >> m;
    rep(i,1,m){
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a + 1, a + m + 1);
}

bool check(int x){
    int j = 1;
    queue<pair<int,int> > q;
    rep(i,1,n){
        while(j <= m && a[j].fi==i){
            q.push(a[j]);
            ++j;
        }
        int cnt = 0;
        while(cnt < x && !q.empty()){
            if(i - q.front().fi > d)
                return 0;
            q.pop();
            ++cnt;
        }
    }
    return q.empty();
}

void process(){
    int l = 1, r = m, res;
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(check(mid)){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << res << '\n';
    queue<pair<int,int> > q;
    int j = 1;
    rep(i,1,n){
        while(j <= m && a[j].fi==i){
            q.push(a[j]);
            ++j;
        }
        int cnt = 0;
        while(cnt < res && !q.empty()){
            cout << q.front().se << ' ';
            q.pop();
            ++cnt;
        }
        cout << 0 << '\n';
    }
}

int main(){
//    readfile();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    inp();
    process();
    return 0;
}

Compilation message

jobs.cpp: In function 'void readfile()':
jobs.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void process()':
jobs.cpp:78:25: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         while(cnt < res && !q.empty()){
      |               ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	2412 KB	Output is correct
2	Correct	36 ms	2532 KB	Output is correct
3	Correct	35 ms	2496 KB	Output is correct
4	Correct	35 ms	2400 KB	Output is correct
5	Correct	36 ms	2460 KB	Output is correct
6	Correct	43 ms	2604 KB	Output is correct
7	Correct	35 ms	2524 KB	Output is correct
8	Correct	35 ms	2460 KB	Output is correct
9	Correct	49 ms	1904 KB	Output is correct
10	Correct	50 ms	1984 KB	Output is correct
11	Correct	39 ms	1596 KB	Output is correct
12	Correct	83 ms	3268 KB	Output is correct
13	Correct	118 ms	4584 KB	Output is correct
14	Correct	182 ms	6432 KB	Output is correct
15	Correct	200 ms	7600 KB	Output is correct
16	Correct	240 ms	9124 KB	Output is correct
17	Correct	288 ms	10564 KB	Output is correct
18	Correct	349 ms	12168 KB	Output is correct
19	Correct	391 ms	13780 KB	Output is correct
20	Correct	327 ms	10556 KB	Output is correct