oj.uz

답안 #145613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145613 2019-08-20T13:49:33 Z cheetose Job Scheduling (CEOI12_jobs) C++11
100 / 100
 349 ms 16864 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n,d,m;
Vi v[100001];
bool ok(int k,bool c)
{
	queue<Pi> q;
	fup(i,1,n,1)
	{
		fup(j,0,(int)v[i].size()-1,1)q.push(mp(v[i][j],i));
		fup(ii,0,k-1,1)
		{
			if(q.empty())break;
			if(i>q.front().Y+d)return 0;
			if(c)printf("%d ",q.front().X);
			q.pop();
		}
		if(c)puts("0");
	}
	return 1;
}
int main() {
	scanf("%d%d%d",&n,&d,&m);
	fup(i,1,m,1)
	{
		int x;
		scanf("%d",&x);
		v[x].pb(i);
	}
	int l=1,r=m;
	while(l<=r)
	{
		int k=(l+r)>>1;
		if(ok(k,0))r=k-1;
		else l=k+1;
	}
	printf("%d\n",l);
	ok(l,1);
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 5048 KB Output is correct
2 Correct 44 ms 4900 KB Output is correct
3 Correct 43 ms 4792 KB Output is correct
4 Correct 43 ms 4852 KB Output is correct
5 Correct 43 ms 4792 KB Output is correct
6 Correct 43 ms 4792 KB Output is correct
7 Correct 43 ms 4792 KB Output is correct
8 Correct 43 ms 4852 KB Output is correct
9 Correct 42 ms 4424 KB Output is correct
10 Correct 41 ms 4416 KB Output is correct
11 Correct 39 ms 4216 KB Output is correct
12 Correct 77 ms 5832 KB Output is correct
13 Correct 114 ms 8104 KB Output is correct
14 Correct 180 ms 10260 KB Output is correct
15 Correct 186 ms 10916 KB Output is correct
16 Correct 247 ms 13688 KB Output is correct
17 Correct 307 ms 16200 KB Output is correct
18 Correct 308 ms 15656 KB Output is correct
19 Correct 349 ms 16864 KB Output is correct
20 Correct 315 ms 16216 KB Output is correct