답안 #917857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917857 2024-01-29T02:10:42 Z oblantis Job Scheduling (CEOI12_jobs) C++17
57 / 100
1000 ms 40536 KB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 2;
int cnt[maxn];
int ls[maxn], a[maxn];
void solve() {
	int n, d, m;
	cin >> n >> d >> m;
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		a[i] = ls[x];
		ls[x] = i;
		cnt[x]++;
	}
	int l = -1, r = 1000001;
	while(l + 1 < r){
		bool ok = 1;
		int mid = l + (r - l) / 2, xl = 1, ex = 0;
		for(int i = 1; i <= n; i++){
			if(i - xl > d){
				ok = 0;
				break;
			}
			ex += mid;
			while(xl <= i && cnt[xl] <= ex){
				ex -= cnt[xl];
				xl++;
			}
			if(xl > i)ex = 0;
		}
		if(ok)r = mid;
		else l = mid;
	}
	cout << r << '\n';
	int xl = 1, ex = 0;
	for(int i = 1; i <= n; i++){
		ex = r;
		while(ex){
			while(xl <= i && cnt[xl] == 0)xl++;
			if(xl > i)break;
			cout << 1 + ls[xl] << ' ';
			ex--;
			ls[xl] = a[ls[xl]];
			cnt[xl]--;
		}
		cout << "0\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1624 KB Output is correct
2 Correct 13 ms 1372 KB Output is correct
3 Correct 11 ms 1372 KB Output is correct
4 Correct 11 ms 1372 KB Output is correct
5 Correct 11 ms 1368 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 11 ms 1372 KB Output is correct
8 Correct 10 ms 1372 KB Output is correct
9 Correct 14 ms 1628 KB Output is correct
10 Correct 15 ms 1624 KB Output is correct
11 Correct 11 ms 1372 KB Output is correct
12 Partially correct 22 ms 2648 KB Partially correct
13 Execution timed out 1016 ms 40536 KB Time limit exceeded
14 Runtime error 18 ms 2904 KB Execution killed with signal 11
15 Runtime error 17 ms 2908 KB Execution killed with signal 11
16 Runtime error 17 ms 2908 KB Execution killed with signal 11
17 Runtime error 18 ms 2908 KB Execution killed with signal 11
18 Runtime error 16 ms 2908 KB Execution killed with signal 11
19 Runtime error 17 ms 2728 KB Execution killed with signal 11
20 Runtime error 17 ms 2904 KB Execution killed with signal 11