Submission #469853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469853	2021-09-02T06:21:21 Z	goatgm03	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	619 ms	33416 KB

jobs

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define v vector
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
const int mx=1e6+5;
int n,d,m;
pair<bool,v<v<int> > > possible(const v<pii>t,int mid){
    int cur=0;
    v<v<int> >res(n);
    for(int day=1;day<=n;day++){
        for(int j=0;j<mid;j++){
            if(t[cur].f>day){
                break;
            }
            if(t[cur].f+d<day)
                return {false,res};
            else if(t[cur].f+d>=day){
                res[day-1].pb(t[cur].s);
                cur++;
            }
            if(cur==m){
                return {true,res};
            }
        }
    }
    return {false,res};
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    // clock_t startTime = clock();
    cin>>n>>d>>m;
    v<v<int> >ans;
    v<pii>t(m);
    for(int i=0;i<m;i++){
        cin>>t[i].f;
        t[i].s=i+1;
    }
    sort(t.begin(),t.begin()+m);
    int lo=1,hi=m,sol=m;
    while(lo<hi){
        int mid=(hi+lo)/2;
        pair<bool,v<v<int> > >c=possible(t,mid);
        if(!c.f){
            lo=mid+1;
        }
        else{
            ans=c.s;
            hi=mid;
        }
    }
    cout<<lo<<endl;
    /*while(lo<hi){
        v<v<int> >result(n+1);
        int mid=(hi+lo)/2;
        int day=1,cur=0;
        bool too_few_machines=false;
        for(int day=1;day<=n;day++){
            for(int j=0;j<mid;j++){
                if(t[cur].f>day){
                    break;
                }
                if(t[cur].f+d>=day){
                    result[day].pb(t[cur].s);
                    cur++;
                }
                else if(t[cur].f+d<day){
                    too_few_machines=true;
                    break;
                }
                if(cur==m)
                    break;
                else if(t[cur].f+d>=day&&t[cur].f<=day){
                    cur++;
                }
            }
        }
        if(!too_few_machines&&cur==m){
            hi=mid;
            sol=min(sol,mid);
            ans=result;    
            // sol=min(sol,mid);
        }
        else{
            lo=mid+1;
        }
        cout<<mid<<endl;
    }
    int day=1,cur=0;
    v<v<int> >each_day(n+1);
    cout<<sol<<endl;
    for(int day=1;day<=n;day++){
        for(int j=0;j<sol;j++){        
            if(t[cur].f>day){
                break;
            }
            if(t[cur].f+d>=day){
                each_day[day].pb(t[cur].s);
                cur++;
            }
        }
    }*/
    for(int i=0;i<n;i++){
        if((int)ans[i].size()==0){
            cout<<"0\n";
            continue;
        }
        for(int j:ans[i])
            cout<<j<<' ';
        cout<<"0\n";
    }
    // cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< endl;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:44:19: warning: unused variable 'sol' [-Wunused-variable]
   44 |     int lo=1,hi=m,sol=m;
      |                   ^~~

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	3832 KB	Output is correct
2	Correct	43 ms	3808 KB	Output is correct
3	Correct	43 ms	3812 KB	Output is correct
4	Correct	44 ms	3812 KB	Output is correct
5	Correct	46 ms	3812 KB	Output is correct
6	Correct	47 ms	3808 KB	Output is correct
7	Correct	45 ms	3832 KB	Output is correct
8	Correct	43 ms	3816 KB	Output is correct
9	Correct	101 ms	10400 KB	Output is correct
10	Correct	116 ms	10452 KB	Output is correct
11	Correct	49 ms	3908 KB	Output is correct
12	Correct	99 ms	7592 KB	Output is correct
13	Correct	145 ms	11704 KB	Output is correct
14	Correct	231 ms	16344 KB	Output is correct
15	Correct	277 ms	17804 KB	Output is correct
16	Correct	326 ms	23120 KB	Output is correct
17	Correct	407 ms	28236 KB	Output is correct
18	Correct	480 ms	30100 KB	Output is correct
19	Runtime error	619 ms	33416 KB	Memory limit exceeded
20	Correct	395 ms	28256 KB	Output is correct