oj.uz

Submission #848309

# Submission time Handle Problem Language Result Execution time Memory
848309 2023-09-12T04:57:09 Z dungz Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 11272 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;
    }
    cout<<0;
}
/*
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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 4512 KB Extra information in the output file
2 Incorrect 484 ms 4672 KB Extra information in the output file
3 Incorrect 490 ms 4412 KB Extra information in the output file
4 Incorrect 481 ms 4304 KB Extra information in the output file
5 Incorrect 492 ms 4304 KB Extra information in the output file
6 Incorrect 495 ms 4416 KB Extra information in the output file
7 Incorrect 505 ms 4560 KB Extra information in the output file
8 Incorrect 515 ms 4556 KB Extra information in the output file
9 Execution timed out 1020 ms 3832 KB Time limit exceeded
10 Execution timed out 1034 ms 3672 KB Time limit exceeded
11 Incorrect 48 ms 4176 KB Extra information in the output file
12 Incorrect 94 ms 6128 KB Extra information in the output file
13 Incorrect 136 ms 7960 KB Extra information in the output file
14 Execution timed out 1022 ms 7204 KB Time limit exceeded
15 Incorrect 232 ms 11004 KB Extra information in the output file
16 Execution timed out 1042 ms 9616 KB Time limit exceeded
17 Execution timed out 1034 ms 11272 KB Time limit exceeded
18 Execution timed out 1039 ms 10320 KB Time limit exceeded
19 Execution timed out 1041 ms 10664 KB Time limit exceeded
20 Execution timed out 1043 ms 11200 KB Time limit exceeded