oj.uz

답안 #79780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79780 2018-10-16T10:56:58 Z psmao Job Scheduling (CEOI12_jobs) C++14
100 / 100
 350 ms 13096 KB 
#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

# 결과 실행 시간 메모리 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