Submission #747771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
747771	2023-05-24T16:40:13 Z	Hyojin	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	1000 ms	17452 KB

jobs

#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) continue;
			if (a[curJob].fi+d>=days) curJob++;
			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) continue;
			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:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1082 ms	1364 KB	Time limit exceeded
2	Execution timed out	1080 ms	1364 KB	Time limit exceeded
3	Execution timed out	1075 ms	1364 KB	Time limit exceeded
4	Execution timed out	1079 ms	1364 KB	Time limit exceeded
5	Execution timed out	1083 ms	1364 KB	Time limit exceeded
6	Execution timed out	1074 ms	1364 KB	Time limit exceeded
7	Execution timed out	1074 ms	1360 KB	Time limit exceeded
8	Execution timed out	1082 ms	1364 KB	Time limit exceeded
9	Execution timed out	1060 ms	1364 KB	Time limit exceeded
10	Execution timed out	1069 ms	1364 KB	Time limit exceeded
11	Correct	102 ms	2508 KB	Output is correct
12	Correct	192 ms	4724 KB	Output is correct
13	Correct	302 ms	7196 KB	Output is correct
14	Execution timed out	1043 ms	4300 KB	Time limit exceeded
15	Correct	503 ms	10556 KB	Output is correct
16	Execution timed out	1025 ms	6116 KB	Time limit exceeded
17	Execution timed out	1040 ms	6912 KB	Time limit exceeded
18	Correct	879 ms	17452 KB	Output is correct
19	Execution timed out	1036 ms	8396 KB	Time limit exceeded
20	Execution timed out	1010 ms	6732 KB	Time limit exceeded