oj.uz

답안 #848314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848314 2023-09-12T05:14:32 Z dungz Job Scheduling (CEOI12_jobs) C++17
100 / 100
 154 ms 13660 KB 
//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O3")
#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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4060 KB Output is correct
2 Correct 16 ms 4060 KB Output is correct
3 Correct 15 ms 4060 KB Output is correct
4 Correct 15 ms 4060 KB Output is correct
5 Correct 20 ms 4060 KB Output is correct
6 Correct 15 ms 4060 KB Output is correct
7 Correct 15 ms 4056 KB Output is correct
8 Correct 15 ms 4060 KB Output is correct
9 Correct 26 ms 4188 KB Output is correct
10 Correct 21 ms 4188 KB Output is correct
11 Correct 15 ms 3928 KB Output is correct
12 Correct 33 ms 4948 KB Output is correct
13 Correct 45 ms 6996 KB Output is correct
14 Correct 71 ms 8276 KB Output is correct
15 Correct 72 ms 9164 KB Output is correct
16 Correct 101 ms 10848 KB Output is correct
17 Correct 119 ms 12792 KB Output is correct
18 Correct 120 ms 12628 KB Output is correct
19 Correct 154 ms 13660 KB Output is correct
20 Correct 120 ms 12784 KB Output is correct