Submission #1153925

#TimeUsernameProblemLanguageResultExecution timeMemory
1153925zhasynJob Scheduling (CEOI12_jobs)C++20
58 / 100
368 ms13944 KiB
//#include "gondola.h" #include <bits/stdc++.h> #define pb push_back #define pf push_front using namespace std; #define F first #define S second typedef long long ll; #define pii pair <int, int> #define pll pair <ll, ll> typedef long double ld; const ll N = 1e6 + 100, M = 1e7 + 10, len = 21, inf = 1e18; const ll mod = 1000000009LL; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll um(ll a, ll b){ return (1LL * a * b) % mod; } ll subr(ll a, ll b){ return ((1LL * a - b) % mod + mod) % mod; } int n, d, from = 0, m; pii a[N]; queue <pii> vec; bool check(int x){ int st = 1; for(int i = 1; i <= n; i++){ if((int)vec.size() > 0){ if(i - vec.front().S > d) return 0; } while(st <= m){ if(a[st].F == i){ vec.push({a[st].S, i}); st++; } else break; } int xx = x; while(xx--){ if((int)vec.size() == 0) break; vec.pop(); } } return true; } void make(int x){ int st = 1; for(int i = 1; i <= n; i++){ vector <int> cur; while(st <= m){ if(a[st].F == i){ vec.push({a[st].S, i}); st++; } else break; } int xx = x; while(xx--){ if((int)vec.size() == 0) break; cout << vec.front().F << " "; vec.pop(); } cout << 0 << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> d >> m; for(int i = 1; i <= m; i++){ cin >> a[i].F; a[i].S = i; } sort(a + 1, a + 1 + m); int l = 0, r = m; while(r - l > 1){ int mid = (l + r) / 2; while(vec.size() != 0){ vec.pop(); } if(check(mid)) r = mid; else l = mid; } cout << r << endl; make(r); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...