Submission #638350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638350	2022-09-05T15:12:22 Z	NONTAC	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	472 ms	20088 KB

jobs

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

int n,m,d;
ii a[1000000];
vector<vector<int> > ans(100001);
bool ok=false;

bool check(int x)
{
    int j=0;
    for(int i=1;i<=n;i++){
        int cnt=x;
        //if(a[j].first> i+d) continue;
        while(cnt && a[j].first + d >= i && j<m && a[j].first <= i){
            cnt--;
            if(ok) ans[i].push_back(a[j].second+1);
            j++;
            if(j==m){
                return true;
            }
        }
    }

    return false;
}

int last_true()
{
    int lo=1, hi=m;
    while(lo<hi){
        int mid=lo + (hi-lo)/2;
        if(check(mid)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }

    ok=true;
    check(lo);

    return lo;
}

int main()
{
    //freopen("test.in","r",stdin);
   // freopen("test.out","w",stdout);


    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].first;
        a[i].second=i;
    }

    sort(a,a+m);

    cout<<last_true()<<endl;

    for(int i=1;i<=n;i++){
        for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
        cout<<0<<endl;
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
      |                     ~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	4548 KB	Output is correct
2	Correct	44 ms	4488 KB	Output is correct
3	Correct	40 ms	4468 KB	Output is correct
4	Correct	40 ms	4460 KB	Output is correct
5	Correct	43 ms	4564 KB	Output is correct
6	Correct	42 ms	4488 KB	Output is correct
7	Correct	42 ms	4576 KB	Output is correct
8	Correct	42 ms	4484 KB	Output is correct
9	Correct	155 ms	4668 KB	Output is correct
10	Correct	149 ms	4812 KB	Output is correct
11	Correct	41 ms	4512 KB	Output is correct
12	Correct	83 ms	6460 KB	Output is correct
13	Correct	119 ms	8892 KB	Output is correct
14	Correct	183 ms	11116 KB	Output is correct
15	Correct	197 ms	11936 KB	Output is correct
16	Correct	259 ms	14220 KB	Output is correct
17	Correct	318 ms	17952 KB	Output is correct
18	Correct	325 ms	18504 KB	Output is correct
19	Correct	472 ms	20088 KB	Output is correct
20	Correct	312 ms	17976 KB	Output is correct