oj.uz

Submission #484128

# Submission time Handle Problem Language Result Execution time Memory
484128 2021-11-02T07:04:29 Z MilosMilutinovic Job Scheduling (CEOI12_jobs) C++14
100 / 100
 207 ms 17184 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010000;
int n,d,m,a[N];
VI qs[N/10];
bool check(int x) {
	deque<int> dq;
	rep(i,1,n+1) {
		for (auto x:qs[i]) dq.pb(i+d);
		int len=min(SZ(dq),x);
		rep(j,0,len) if (dq[0]<i) return false;
		rep(j,0,len) dq.pop_front();
	}
	return dq.empty();
}
void rec(int x) {
	deque<int> dq;
	rep(i,1,n+1) {
		for (auto x:qs[i]) dq.pb(x);
		int len=min(SZ(dq),x);
		rep(j,0,len) {
			printf("%d ",dq[0]);
			dq.pop_front();
		}
		printf("0\n");
	}
}
int main() {
	scanf("%d%d%d",&n,&d,&m);
	rep(i,1,m+1) scanf("%d",a+i),qs[a[i]].pb(i);
	int l=1,r=m,ans=0;
	while (l<=r) {
		int md=(l+r)>>1;
		if (check(md)) ans=md,r=md-1;
		else l=md+1;
	}
	printf("%d\n",ans);
	rec(ans);
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:28:13: warning: unused variable 'x' [-Wunused-variable]
   28 |   for (auto x:qs[i]) dq.pb(i+d);
      |             ^
jobs.cpp: In function 'int main()':
jobs.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d",&n,&d,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:49:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  rep(i,1,m+1) scanf("%d",a+i),qs[a[i]].pb(i);
      |               ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4420 KB Output is correct
2 Correct 22 ms 4412 KB Output is correct
3 Correct 22 ms 4480 KB Output is correct
4 Correct 21 ms 4420 KB Output is correct
5 Correct 22 ms 4408 KB Output is correct
6 Correct 22 ms 4412 KB Output is correct
7 Correct 21 ms 4440 KB Output is correct
8 Correct 21 ms 4456 KB Output is correct
9 Correct 27 ms 4408 KB Output is correct
10 Correct 26 ms 4508 KB Output is correct
11 Correct 23 ms 4164 KB Output is correct
12 Correct 46 ms 5808 KB Output is correct
13 Correct 72 ms 8032 KB Output is correct
14 Correct 106 ms 9712 KB Output is correct
15 Correct 112 ms 11024 KB Output is correct
16 Correct 147 ms 13124 KB Output is correct
17 Correct 174 ms 15420 KB Output is correct
18 Correct 177 ms 15684 KB Output is correct
19 Correct 207 ms 17184 KB Output is correct
20 Correct 176 ms 15428 KB Output is correct