oj.uz

Submission #140539

# Submission time Handle Problem Language Result Execution time Memory
140539 2019-08-03T12:57:43 Z path Job Scheduling (CEOI12_jobs) C++14
100 / 100
 500 ms 15108 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long int ll;
const int N=1e6+3;
int n,d,m;
pair<int,int> a[N];
bool chk(int x){
    queue < pair<int,int> > q;
    pair<int,int> tmp;
    for(int i=0;i<m;i++)
        q.push(make_pair(a[i].f,a[i].f+d));
    for(int i=1;i<=n&&q.size();i++){
        for(int j=0;j<x&&q.size();j++){
            tmp=q.front();
            if(tmp.s<i) return 0;
            if(tmp.f>i) break;
            q.pop();
        }
    }
    return (!q.size());
}
void out (int x){
    int tmp=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<x&&tmp<m;j++){
            cout<<a[tmp].s<<" ";
            tmp++;
        }
        cout<<0<<'\n';
    }
    return;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].f;
        a[i].s=i+1;
    }
    sort(a,a+m);
    int s=1,e=m,mid;
    while(s<=e){
        mid=(s+e)/2;
        if(chk(mid))
            e=mid-1;
        else
            s=mid+1;
    }
    e++;
    cout<<e<<'\n';
    out(e);
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2140 KB Output is correct
2 Correct 39 ms 2108 KB Output is correct
3 Correct 39 ms 2104 KB Output is correct
4 Correct 39 ms 2148 KB Output is correct
5 Correct 39 ms 2116 KB Output is correct
6 Correct 39 ms 2140 KB Output is correct
7 Correct 39 ms 2140 KB Output is correct
8 Correct 39 ms 2104 KB Output is correct
9 Correct 54 ms 2240 KB Output is correct
10 Correct 54 ms 2172 KB Output is correct
11 Correct 47 ms 2096 KB Output is correct
12 Correct 100 ms 3704 KB Output is correct
13 Correct 151 ms 5384 KB Output is correct
14 Correct 207 ms 6944 KB Output is correct
15 Correct 284 ms 8596 KB Output is correct
16 Correct 323 ms 10148 KB Output is correct
17 Correct 390 ms 11748 KB Output is correct
18 Correct 440 ms 13512 KB Output is correct
19 Correct 500 ms 15108 KB Output is correct
20 Correct 383 ms 11724 KB Output is correct