oj.uz

답안 #747772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747772 2023-05-24T16:41:51 Z Hyojin Job Scheduling (CEOI12_jobs) C++17
100 / 100
 256 ms 20308 KB 
#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define deb(x) cerr << #x << ' ' << x << '\n'
const int base=31;
const int MOD=1e9+7;
const int N=1e6+5;
void setIO(const string &NAME)
{
	if (NAME.size())
	{
		freopen((NAME+".inp").c_str(),"r",stdin);
		freopen((NAME+".out").c_str(),"w",stdout);
	}
}
int n,m,d;
pii a[N];
bool check(int x)
{
	int curJob=1;
	for (int days=1;days<=n;days++)
	{
		for (int machine=1;machine<=x;machine++)
		{
			if (a[curJob].fi>days) break;
			if (a[curJob].fi+d>=days) curJob++;
			else return false;
			if (curJob==m) return true;
		}
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef izumiShiho
    	setIO("input");
	#endif //izumiShiho
    cin>>n>>d>>m;
    for (int i=1;i<=m;i++) 
    {
    	cin>>a[i].fi;
    	a[i].se=i;
    }
    sort(a+1,a+m+1);
	int l=1,r=m;
	while (l<=r)
	{
		int mid=l+r>>1;
		if (check(mid)) r=mid-1;
		else l=mid+1;
	}
	cout<<r+1<<"\n";
	vector<vector<int>>ans;
	ans.resize(n+1);
	int x=r+1;
	int curJob=1;
	for (int days=1;days<=n;days++)
	{
		for (int machine=1;machine<=x;machine++)
		{
			if (a[curJob].fi>days) break;
			if (a[curJob].fi+d>=days) 
			{
				ans[days].pb(a[curJob].se);
				curJob++;
			}
			if (curJob==m) break;
		}
		if (curJob==m) break;
	}
	for (int i=1;i<=n;i++)
	{
		for (auto x:ans[i]) cout<<x<<' ';
		cout<<0<<"\n";
	}
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid=l+r>>1;
      |           ~^~
jobs.cpp: In function 'void setIO(const string&)':
jobs.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen((NAME+".inp").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen((NAME+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2388 KB Output is correct
2 Correct 17 ms 2388 KB Output is correct
3 Correct 18 ms 2432 KB Output is correct
4 Correct 17 ms 2500 KB Output is correct
5 Correct 18 ms 2380 KB Output is correct
6 Correct 18 ms 2388 KB Output is correct
7 Correct 18 ms 2388 KB Output is correct
8 Correct 17 ms 2376 KB Output is correct
9 Correct 32 ms 4680 KB Output is correct
10 Correct 34 ms 4736 KB Output is correct
11 Correct 26 ms 2252 KB Output is correct
12 Correct 52 ms 4100 KB Output is correct
13 Correct 79 ms 6704 KB Output is correct
14 Correct 110 ms 8956 KB Output is correct
15 Correct 131 ms 9676 KB Output is correct
16 Correct 161 ms 12032 KB Output is correct
17 Correct 197 ms 15900 KB Output is correct
18 Correct 213 ms 16332 KB Output is correct
19 Correct 256 ms 20308 KB Output is correct
20 Correct 196 ms 15944 KB Output is correct