oj.uz

Submission #56446

# Submission time Handle Problem Language Result Execution time Memory
56446 2018-07-11T10:54:09 Z Batrr Job Scheduling (CEOI12_jobs) C++14
100 / 100
 689 ms 23312 KB 
#include <bits/stdc++.h>

#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define o cout<<"BUG"<<endl;
#define IOS ios_base::sync_with_stdio(0);
using namespace std;                    
const ll maxn=1e6+123,inf=1e18,mod=1e9+7;
int n,m,d,b[maxn];
pair<int,int>a[maxn];
bool check(int mx,bool flag){
    queue<int>q;
    for(int i=1,j=0;i<=n;i++){
        while(j<m && a[j].f==i)
            q.push(a[j++].s);
        int cur=mx;
        while(!q.empty() && cur){
            if(b[q.front()]+d<i)
                return 0;
            if(flag)
                cout<<q.front()<<" ";
            q.pop();
            cur--;
        }
        if(flag)
            cout<<0<<endl;
    }
    return q.empty();
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif
    IOS
    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].f;
        a[i].s=i+1;
        b[i+1]=a[i].f;
    }
    sort(a,a+m);
    int l=1,r=1e6;
    while(l<=r){
        int m=(l+r)/2;
        if( !check(m,0) )
            l=m+1;
        else
            r=m-1;
    }
    cout<<l<<endl;
    check(l,1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2552 KB Output is correct
2 Correct 56 ms 2596 KB Output is correct
3 Correct 78 ms 2596 KB Output is correct
4 Correct 56 ms 2676 KB Output is correct
5 Correct 79 ms 2760 KB Output is correct
6 Correct 57 ms 2816 KB Output is correct
7 Correct 55 ms 2816 KB Output is correct
8 Correct 87 ms 2816 KB Output is correct
9 Correct 235 ms 2816 KB Output is correct
10 Correct 216 ms 2816 KB Output is correct
11 Correct 56 ms 2816 KB Output is correct
12 Correct 139 ms 4320 KB Output is correct
13 Correct 165 ms 6196 KB Output is correct
14 Correct 365 ms 8188 KB Output is correct
15 Correct 328 ms 9900 KB Output is correct
16 Correct 459 ms 11776 KB Output is correct
17 Correct 537 ms 13740 KB Output is correct
18 Correct 483 ms 18476 KB Output is correct
19 Correct 689 ms 23312 KB Output is correct
20 Correct 548 ms 23312 KB Output is correct