제출 #1204933

#제출 시각아이디문제언어결과실행 시간메모리
1204933MighilonJob Scheduling (CEOI12_jobs)C++20
40 / 100
313 ms30752 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; void solve(){ int n,d,m; cin>>n>>d>>m; vector<vi> a(n); F0R(i,m){ int x; cin>>x;--x; a[x].pb(i); } priority_queue<pi,vpi,greater<pi>> pq; vector<vpi> ans; // ans.push_back(vpi()); F0R(i,n){ trav(j,a[i]){ pq.push({i,j}); } while(!pq.empty()&&pq.top().f+d<i){ vpi tmp; int cur=pq.top().f; while(!pq.empty()&&pq.top().f+d>=cur&&pq.top().f<=cur&&cur<i){ dbg(cur) auto [t,id] = pq.top(); pq.pop(); tmp.pb({cur,id}); cur=max(cur+1,pq.empty()?-1:pq.top().f); } dbg(i) dbg(tmp) ans.pb(tmp); } trav(j,ans){ if(!pq.empty()){ auto [t,id] = pq.top(); pq.pop(); j.pb({i,id}); } } } while(!pq.empty()&&pq.top().f+d<n+1){ vpi tmp; int cur=pq.top().f; while(!pq.empty()&&pq.top().f+d>=cur&&pq.top().f<=cur&&cur<n+1){ auto [t,id] = pq.top(); pq.pop(); tmp.pb({cur,id}); cur++; } dbg(tmp) ans.pb(tmp); } dbg(ans) vector<vi> mp(n); trav(i,ans){ trav(j,i){ mp[j.f].pb(j.s); } } cout<<sz(ans)<<nl; F0R(i,n){ trav(j,mp[i]){ cout<<j+1<<" "; } cout<<"0\n"; } } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; // cin >> TC; while(TC--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...