Submission #99882

#	Time	Username	Problem	Language	Result	Execution time	Memory
99882		bharat2002	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	116 ms	33792 KiB

jobs

/*input
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
pii arr[N];int n, m, d, oriarr[N];vector<int> days[N];
bool p(int x){
	for(int i=1;i<=n;i++) days[i].clear();
	int ptr=1;
	for(int i=1;i<=n;i++)
	{
		while(ptr<=m&&arr[ptr].f<=i&&days[i].size()<x) days[i].push_back(arr[ptr++].s);
		for(auto j:days[i])
		{
			if(i>=oriarr[j]&&i+d>=oriarr[j]) continue;return false;
		}
	}
	if(ptr<=m) return false;
	return true;
}
bool sf(pii a, pii b){
	return a.f<b.f;
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>arr[i].f;arr[i].s=i;oriarr[i]=arr[i].f;
	}
	sort(arr+1, arr+m+1, sf);
	int low=1, high=m;
/*	cout<<n<<endl<<endl;
	if(p(2))
	{
		cout<<"YS\n";
	}
	for(int i=1;i<=n;i++)
	{
		for(auto j:days[i]) cout<<"{"<<j<<" "<<oriarr[j]<<"} ";cout<<endl;
	}*/
	while(low<high)
	{
		int mid=(low+high)/2;
		if(p(mid)) high=mid;
		else low=mid+1;
	}
	p(low);
	cout<<low<<endl;
	for(int i=1;i<=n;i++)
	{
		for(auto j:days[i]) cout<<j<<" ";cout<<0<<endl;
	}
}

Compilation message (stderr)

jobs.cpp: In function 'bool p(long long int)':
jobs.cpp:21:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<=m&&arr[ptr].f<=i&&days[i].size()<x) days[i].push_back(arr[ptr++].s);
                                ~~~~~~~~~~~~~~^~
jobs.cpp:24:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(i>=oriarr[j]&&i+d>=oriarr[j]) continue;return false;
    ^~
jobs.cpp:24:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(i>=oriarr[j]&&i+d>=oriarr[j]) continue;return false;
                                              ^~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:62:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto j:days[i]) cout<<j<<" ";cout<<0<<endl;
   ^~~
jobs.cpp:62:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto j:days[i]) cout<<j<<" ";cout<<0<<endl;
                                    ^~~~

• Subtask 1: 10 / 100