oj.uz

Submission #848310

# Submission time Handle Problem Language Result Execution time Memory
848310 2023-09-12T04:58:43 Z dungz Job Scheduling (CEOI12_jobs) C++17
60 / 100
 1000 ms 9160 KB 
//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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 4048 KB Output is correct
2 Correct 493 ms 4464 KB Output is correct
3 Correct 483 ms 4048 KB Output is correct
4 Correct 501 ms 4108 KB Output is correct
5 Correct 486 ms 4212 KB Output is correct
6 Correct 502 ms 4208 KB Output is correct
7 Correct 507 ms 4460 KB Output is correct
8 Correct 499 ms 4300 KB Output is correct
9 Execution timed out 1049 ms 3416 KB Time limit exceeded
10 Execution timed out 1049 ms 3416 KB Time limit exceeded
11 Correct 48 ms 3920 KB Output is correct
12 Correct 90 ms 4948 KB Output is correct
13 Correct 149 ms 7020 KB Output is correct
14 Execution timed out 1024 ms 5440 KB Time limit exceeded
15 Correct 245 ms 9160 KB Output is correct
16 Execution timed out 1045 ms 6736 KB Time limit exceeded
17 Execution timed out 1037 ms 7760 KB Time limit exceeded
18 Execution timed out 1039 ms 7180 KB Time limit exceeded
19 Execution timed out 1026 ms 7124 KB Time limit exceeded
20 Execution timed out 1042 ms 7912 KB Time limit exceeded