oj.uz

Submission #1109014

# Submission time Handle Problem Language Result Execution time Memory
1109014 2024-11-05T18:53:30 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 313 ms 41156 KB 
/*************
  the author:     
  shimutski_zoro   
************ */
#include <bits/stdc++.h>
using namespace std;
#define yon(x) cout<<((x)?"YES":"NO");
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first 
#define ss second
#define em emplace_back
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=k;i>=j;i--)
#define forp(x,y,a) for(auto &[x,y]:(a))
typedef long long  ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;
typedef vector<string> vs;
typedef deque<ll> dl;
const int mod=1e9+7;
ll inf =1e18+1;
const int M=1e6;
const int N=1e3+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void solve(){
ll n,m,d;
cin>>n>>d>>m;
vpl a(m);
rep(i,0,m-1)cin>>a[i].ff , a[i].ss=i+1;
sort(all(a));
//forp(x,y,a)cout<<x<<" "<<y<<"\n";
vvl tmp(n);
 function<bool(ll)>check=[&](ll r)->bool{
  tmp=vvl (n);
ll cnt=0;
rep(i,1,n){
  rep(j,1,r){
    if(a[cnt].ff>i)
    break;
if(a[cnt].ff+d<i){
return 0;
}else{
  tmp[i-1].em(a[cnt].ss);
  cnt++;
}
if(cnt>=m)return 1;
  }

}
return 0;

 };
 vvl v(n);
 ll lo=1,hi=1e9;
 ll ans=m;
 while(lo<=hi){
  ll mid= lo + (hi-lo)/2;
if(check(mid)){
  hi=mid-1;
  ans=mid;
  v=tmp;
}else{
  lo=mid+1;
}
 }
cout<<ans<<endl;
//vvl v(n+1);
rep(i,0,n-1){
  for(auto it:v[i]){
    cout<<it<<" ";
  }
  cout<<0<<"\n";
}
}


signed main()
{
 
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #ifdef Usaco
    string f="herding";
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
    #endif
   int t = 1;
//cin >> t;
    while (t--)
    {
      solve();
    //  if(t>0)
      //cout<<endl;
    }
}
/*
*/

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6136 KB Output is correct
2 Correct 44 ms 6072 KB Output is correct
3 Correct 61 ms 6148 KB Output is correct
4 Correct 42 ms 6148 KB Output is correct
5 Correct 39 ms 6092 KB Output is correct
6 Correct 44 ms 6020 KB Output is correct
7 Correct 44 ms 6144 KB Output is correct
8 Correct 59 ms 6148 KB Output is correct
9 Correct 58 ms 13460 KB Output is correct
10 Correct 61 ms 13528 KB Output is correct
11 Correct 37 ms 4664 KB Output is correct
12 Correct 66 ms 8868 KB Output is correct
13 Correct 105 ms 14060 KB Output is correct
14 Correct 164 ms 19492 KB Output is correct
15 Correct 146 ms 20832 KB Output is correct
16 Correct 252 ms 26860 KB Output is correct
17 Runtime error 277 ms 33484 KB Memory limit exceeded
18 Runtime error 261 ms 34868 KB Memory limit exceeded
19 Runtime error 313 ms 41156 KB Memory limit exceeded
20 Runtime error 292 ms 33492 KB Memory limit exceeded