oj.uz

Submission #165955

# Submission time Handle Problem Language Result Execution time Memory
165955 2019-11-29T20:11:15 Z reda Job Scheduling (CEOI12_jobs) C++14
100 / 100
 640 ms 16888 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define endl  '\n'
int n ,  m ,  d;
const  int MAXN = 1e5 +7 ;
vector<int> adj[MAXN];
bool  bs(int mid ,  bool  h )
{
  queue<pii> q;
  for(int i = 1 ;i <=n;i++){
  for(auto j : adj[i])
    q.push({i,j});
  for(int j = 0 ;j <mid && q.size() ;j++)
  {
    if(i-q.front().fi >d)return 0;
    if(h)cout<<q.front().se<<' ';
q.pop();
  }
  if(h) cout<<'0'<<endl;
}
return 1 ;
}
int  main ()
{
  cin >> n >> d >> m;
	for(int i = 1 ;i <= m ;i++)
	{
		int h ;
		cin>>h;
		adj[h].pb(i);
	}
  int l = 1 , r = m ;
  while(l!=r)
  {
    int mid = (l+r)/2;
    if(bs(mid,0))r=mid;
    else l =mid+1;
  }
  cout<<l<<endl;
  bs(l,1);
  return 0 ;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4844 KB Output is correct
2 Correct 67 ms 4772 KB Output is correct
3 Correct 67 ms 4784 KB Output is correct
4 Correct 67 ms 4748 KB Output is correct
5 Correct 67 ms 4848 KB Output is correct
6 Correct 68 ms 4820 KB Output is correct
7 Correct 67 ms 4876 KB Output is correct
8 Correct 67 ms 4840 KB Output is correct
9 Correct 68 ms 4344 KB Output is correct
10 Correct 69 ms 4348 KB Output is correct
11 Correct 67 ms 4216 KB Output is correct
12 Correct 134 ms 5948 KB Output is correct
13 Correct 197 ms 7932 KB Output is correct
14 Correct 305 ms 10328 KB Output is correct
15 Correct 321 ms 11000 KB Output is correct
16 Correct 457 ms 13884 KB Output is correct
17 Correct 580 ms 16060 KB Output is correct
18 Correct 640 ms 15688 KB Output is correct
19 Correct 606 ms 16888 KB Output is correct
20 Correct 549 ms 16072 KB Output is correct