Submission #848310

#	Time	Username	Problem	Language	Result	Execution time	Memory
848310		dungz	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1049 ms	9160 KiB

jobs

//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<int> b[100005];
int n,d,m;
bool check(int x)
{
    deque<int> de;
    for(int i=1;i<=n;i++)
    {
        for(auto j:b[i]) 
        {
        	de.push_back(i);
		}
//		for(auto j:de) cout<<j<<" ";
//        cout<<endl;
        for(int j=1;j<=x;j++)
        {
        	if(!de.empty())
        	{
        		if(de.front()+d<i)
        		{
//        			cout<<i;
        			return 0;
				}
      	    	de.pop_front();
			}
        }
    }
    if(de.size()) return 0;
    return 1;
}
int main(){
//    #ifndef ONLINE_JUDGE
//           freopen (task".inp", "r", stdin);
//           freopen (task".out", "w", stdout);
//    #endif
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        b[x].push_back(i);
    }
    int l=1,r=m,ans=m;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    deque<int> de;
    for(int i=1;i<=n;i++)
    {
		for(auto j:b[i]) de.push_back(j);
		for(int j=1;j<=ans;j++)
		{
			if(!de.empty())
			{
				cout<<de.front()<<" ";
				de.pop_front();
			}
		}
		cout<<0<<endl;
    }
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:24:18: warning: unused variable 'j' [-Wunused-variable]
   24 |         for(auto j:b[i])
      |                  ^

• Subtask 1: 60 / 100