oj.uz

Submission #143892

# Submission time Handle Problem Language Result Execution time Memory
143892 2019-08-15T12:16:01 Z miguel Job Scheduling (CEOI12_jobs) C++14
100 / 100
 93 ms 512 KB 
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define mp make_pair
const ll mod = 1000000007;
const ll nmax=1000003;
int n, d, m, cnt[100010];

bool check(int xd){
    multiset<pi> s;
    for(int i=1; i<=n; i++){
        int aval=xd;
        if(cnt[i]) s.insert({i, cnt[i]});
        //if(xd==2){dbg(i); for(pi j: s) cout<<j.x<<" "<<j.y<<endl;}
        if(s.size() && (*s.begin()).x<i-d) return 0;
        while(aval && s.size()){
            pi cur=*s.begin();
            if(aval>=cur.y){
                s.erase(s.begin());
                aval-=cur.y;
            }
            else{
                s.erase(s.begin());
                s.insert({cur.x, cur.y-aval});
                aval=0;
            }
        }
    }
    if(s.size()==0) return 1;
    else return 0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>d>>m;
    for(int i=1, x; i<=m; i++){
        cin>>x;
        cnt[x]++;
    }
    //for(int i=1; i<=n; i++) cout<<cnt[i]<<" "; cout<<endl;
    int l=0, r=m;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
    for(int i=1; i<=n; i++)cout<<0<<"\n"; cout<<endl;
    return 0;
}

Compilation message

jobs.cpp: In function 'int32_t main()':
jobs.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1; i<=n; i++)cout<<0<<"\n"; cout<<endl;
     ^~~
jobs.cpp:77:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i=1; i<=n; i++)cout<<0<<"\n"; cout<<endl;
                                           ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 11 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 11 ms 504 KB Output is correct
6 Correct 11 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 11 ms 504 KB Output is correct
9 Correct 19 ms 504 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 12 ms 376 KB Output is correct
12 Correct 22 ms 376 KB Output is correct
13 Correct 30 ms 376 KB Output is correct
14 Correct 55 ms 456 KB Output is correct
15 Correct 47 ms 376 KB Output is correct
16 Correct 71 ms 376 KB Output is correct
17 Correct 83 ms 376 KB Output is correct
18 Correct 75 ms 504 KB Output is correct
19 Correct 93 ms 512 KB Output is correct
20 Correct 83 ms 504 KB Output is correct