oj.uz

Submission #515797

# Submission time Handle Problem Language Result Execution time Memory
515797 2022-01-19T17:43:58 Z perchuts Job Scheduling (CEOI12_jobs) C++17
100 / 100
 331 ms 14728 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ii v[10*maxn];
int n,m,d;
bool possible(int x){
    queue<int>q;
    int it = 1;
    for(int i=1;i<=n;i++){
       while(it<=m&&v[it].first==i)q.push(i),it++;
        for(int j=1;j<=x&&!q.empty();j++){
            int k = q.front();q.pop();
            if(k+d<i)return 0;
        }
    }
    return 1;
}



int main(){_
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int day;
        cin>>day;
        v[i] = {day,i};
    }    
    sort(v+1,v+1+m);
    int l = 1, r = m,ans;
    while(l<=r){
        int md = l + (r-l+1)/2;
        if(possible(md)){
            ans = md,r=md-1;
        }else{
            l = md+1;
        }
    }
    int x = ans,it = 1;
    queue<ii>q;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        while(it<=m&&v[it].first==i&&it<=m)q.push(v[it++]);
        for(int j=1;j<=x&&!q.empty();j++){
            auto [k,id] = q.front();q.pop();
            cout<<id<<" ";
        }
        cout<<"0\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:59:25: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |         for(int j=1;j<=x&&!q.empty();j++){
      |                     ~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2592 KB Output is correct
2 Correct 28 ms 2604 KB Output is correct
3 Correct 35 ms 2568 KB Output is correct
4 Correct 26 ms 2504 KB Output is correct
5 Correct 29 ms 2552 KB Output is correct
6 Correct 32 ms 2460 KB Output is correct
7 Correct 27 ms 2480 KB Output is correct
8 Correct 26 ms 2612 KB Output is correct
9 Correct 36 ms 2116 KB Output is correct
10 Correct 38 ms 2112 KB Output is correct
11 Correct 34 ms 1596 KB Output is correct
12 Correct 72 ms 3280 KB Output is correct
13 Correct 100 ms 4584 KB Output is correct
14 Correct 142 ms 6492 KB Output is correct
15 Correct 173 ms 7596 KB Output is correct
16 Correct 212 ms 9160 KB Output is correct
17 Correct 254 ms 11156 KB Output is correct
18 Correct 285 ms 12548 KB Output is correct
19 Correct 331 ms 14728 KB Output is correct
20 Correct 266 ms 11236 KB Output is correct