Submission #79780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
79780	2018-10-16T10:56:58 Z	psmao	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	350 ms	13096 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 1000050;

int n, d, m;
pair<int,int> a[maxn];

bool jud(int x)
{
	int j = 1, tmp = 0;
	for(int i = 1; i <= n; ++ i)
	{
		if(j > m) break;
		if(a[j].fi > i) continue;
		tmp = x;
		while(j <= m && a[j].fi + d >= i && tmp > 0) {-- tmp; ++ j;}
	}
	return (j > m);
}
void go(int x)
{
	int j = 1, tmp = 0;
	for(int i = 1; i <= n; ++ i)
	{
		tmp = x;
		while(j <= m && a[j].fi + d >= i && tmp > 0) {pf("%d ",a[j].se); -- tmp; ++ j;}
		pf("0\n");
	}	
}
int main()
{
	#ifdef MPS
		fp("1.in","r",stdin);
		fp("1.out","w",stdout);
		db mps = clock();
	#endif
	sf("%d%d%d",&n,&d,&m);
	fo(i,1,m) sf("%d",&a[i].fi), a[i].se = i;
	sort(a+1,a+m+1);
	int l = 1, r = m, mid, ans = -1;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(jud(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	pf("%d\n",ans);
	go(mid);
	#ifdef MPS
		pf("Time Elapsed: %.3fms\n",clock()-mps);
	#endif
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:67:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d%d%d",&n,&d,&m);
    ^
jobs.cpp:68:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,1,m) sf("%d",&a[i].fi), a[i].se = i;
                             ^
jobs.cpp:78:4: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  go(mid);
  ~~^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1656 KB	Output is correct
2	Correct	32 ms	1924 KB	Output is correct
3	Correct	27 ms	1924 KB	Output is correct
4	Correct	30 ms	1924 KB	Output is correct
5	Correct	28 ms	1924 KB	Output is correct
6	Correct	28 ms	1924 KB	Output is correct
7	Correct	31 ms	2096 KB	Output is correct
8	Correct	29 ms	2096 KB	Output is correct
9	Correct	42 ms	2188 KB	Output is correct
10	Correct	46 ms	2188 KB	Output is correct
11	Correct	38 ms	2188 KB	Output is correct
12	Correct	78 ms	3468 KB	Output is correct
13	Correct	135 ms	4876 KB	Output is correct
14	Correct	176 ms	6392 KB	Output is correct
15	Correct	221 ms	7848 KB	Output is correct
16	Correct	241 ms	9384 KB	Output is correct
17	Correct	282 ms	10792 KB	Output is correct
18	Correct	311 ms	12228 KB	Output is correct
19	Correct	350 ms	13096 KB	Output is correct
20	Correct	279 ms	13096 KB	Output is correct