제출 #493351

#제출 시각아이디문제언어결과실행 시간메모리
493351PikaQJob Scheduling (CEOI12_jobs)C++17
60 / 100
251 ms13744 KiB
#include<bits/stdc++.h> // #define int ll #define forn(i,n) for(int i=0;i<(n);i++) #define Forn(i,n) for(int i=1;i<=(n);i++) #define ll long long #define pb push_back #define F first #define S second #define lb lower_bound #define ub upper_bound #define rz resize #define vi vector<int> #define vl vector<long long> #define vpi vector<pair<int,int> > #define pii pair<int,int> #define pll pair<long long,long long> #define mp make_pair #define all(p) p.begin(),p.end() #define alr(p,q) p+1,p+q+1 #define ull unsigned long long #define st0(p) memset((p),0,sizeof(p)) #define T(x) ((x)%2 ? s[(x)/2] : '.') #define lowb(x) x&-x #define ls(x) (x)*2 #define rs(x) (x)*2+1 using namespace std; inline void USACO(const string &s){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} // template <class T> int max(T a, T ... b) { cout << a << " "; debug(b...);} #define fail() {cout << "-1\n";return;} const int INF = 1e9+7; const int N = 1e6+9; int n,d,m; vpi a; bool check(int x){ int cur = 1,res = x; for(auto &i : a){ if(cur > i.F + d) return 0; if(cur < i.F ) cur++,res = x; res--; if(res == 0) cur++,res = x; } return 1; } void out(int x){ int cur = 1,res = x; for(auto &i : a){ if(cur < i.F || res == 0){ cout << "0\n"; cur++,res = x; } cout << i.S << ' '; res--; } while(cur <= n) cur++,cout << "0\n"; } void solve(){ cin >> n >> d >> m; a.rz(m); forn(i,m) cin >> a[i].F,a[i].S = i+1; sort(all(a)); int lo =0,hi = n; while(lo != hi-1){ int mid = (lo+hi)/2; if(check(mid)) hi = mid; else lo = mid; } cout << hi << '\n'; out(hi); } signed main(){ // USACO("sabotage"); cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); // int t; // cin >> t; // while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...