Submission #571037

#	Time	Username	Problem	Language	Result	Execution time	Memory
571037		elesis	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	480 ms	46276 KiB

jobs

    #include<bits/stdc++.h>
    using namespace std;
    #define fast ios_base::sync_with_stdio(false);cin.tie(0);
    #define int long long 
    #define pii pair<int,int> 
    #define ff first
    #define ss second
    /*
    int binpow(int a,int b,int m) {
        a %= m;
        int res = 1;
        while(b>0) {
            if (b&1)
            {
                res=res*a%m;
            }
            a=a*a%m;
            b>>=1;
        }
        return res;
    }
    */
    int N,M,D;
    pair<bool, vector<vector <int>>> ok(vector<pii> &arr, int x)
    {
    	vector <vector <int>> nub(N);
    	int job=0;
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=0;j<x;j++)
    		{
    			if(arr[job].ff>i)
    			{
    				break;
    			}
    			if(arr[job].ff+D>=i)
    			{
    				nub[i-1].push_back(arr[job].ss);
    				job++;
    			}
    			else
    			{
    				return {false,nub};
    			}
    			if(job==M)
    			{
    				return {true,nub};
    			}
    		}
    	}
    	return {false,nub};
    }
     
    void solve()
    {
        cin>>N>>D>>M;
        int ans;
        vector <pii> arr(M);
        for(int i=0;i<M;i++)
        {
            cin>>arr[i].first;
            arr[i].second=i+1;
        }
        sort(arr.begin(),arr.end());
        vector <vector <int>> res;
        int lo=1,hi=M;
        while(lo<hi)
        {
            int mid=(lo+hi)/2;
            pair <bool,vector <vector <int>>> ef=ok(arr,mid);
            if(ef.ff)
            {
                ans=mid;
                res=ef.ss;
                hi=mid;
            }
            else
            {
                lo=mid+1;
            }
        }
        cout << lo << "\n";
        for(int i=0;i<N;i++)
        {
            for(auto &it:res[i])
            {
                cout << it << " " ;
            }
            cout << 0 << "\n";
        }
    }
    signed main()
    {
        fast
        clock_t start, end;
        start = clock();
        solve();
        end = clock();
        double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
        //cout << "time taken" << " " << time_taken << "\n";
    }

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:57:13: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   57 |         int ans;
      |             ^~~
jobs.cpp: In function 'int main()':
jobs.cpp:99:16: warning: unused variable 'time_taken' [-Wunused-variable]
   99 |         double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |                ^~~~~~~~~~

• Subtask 1: 80 / 100