Submission #453104

#TimeUsernameProblemLanguageResultExecution timeMemory
453104KhizriJob Scheduling (CEOI12_jobs)C++17
25 / 100
313 ms13820 KiB
#include <bits/stdc++.h> using namespace std; //------------------------------DEFINE------------------------------ //****************************************************************** #define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0) #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) #define endl "\n" //****************************************************************** //----------------------------FUNCTION------------------------------ //****************************************************************** ll gcd(ll a,ll b){ if(a>b) swap(a,b); if(a==0) return a+b; return gcd(b%a,a); } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } bool is_prime(ll n){ ll k=sqrt(n); if(n==2) return true; if(n<2||n%2==0||k*k==n) return false; for(int i=3;i<=k;i+=2){ if(n%i==0){ return false; } } return true; } //***************************************************************** //--------------------------MAIN-CODE------------------------------ const int mxn=1e6+5; int t=1,n,d,m; vector<pii>arr; bool check(int k){ int x=1,say=0; for(int i=0;i<m;i++){ if(arr[i].F>x){ x=arr[i].F; say=1; } else{ say++; if(x-arr[i].F>d||x>n){ return false; } } if(say>=k){ say=0; x++; } } return true; } void f(int k){ int x=1,say=0; for(int i=0;i<m;i++){ if(arr[i].F>x){ for(int j=x+1;j<arr[i].F;j++){ cout<<0<<endl; } x=arr[i].F; cout<<arr[i].S<<' '; } else{ say++; cout<<arr[i].S<<' '; } if(say>=k){ say=0; x++; cout<<0<<endl; } } for(int i=x;i<=n;i++){ cout<<0<<endl; } } void solve(){ cin>>n>>d>>m; for(int i=1;i<=m;i++){ int q; cin>>q; arr.pb({q,i}); } sort(all(arr)); int l=1,r=n,ans=1; while(l<=r){ int mm=(l+r)/2; if(check(mm)){ r=mm-1; ans=mm; } else{ l=mm+1; } } cout<<ans<<endl; f(ans); } int main(){ IOS; //cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...