oj.uz

Submission #1109005

# Submission time Handle Problem Language Result Execution time Memory
1109005 2024-11-05T18:42:12 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 292 ms 44708 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;
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;
 ll lo=1,hi=m+1;
 while(lo<=hi){
  ll mid= lo + (hi-lo)/2;
if(check(mid)){
  hi=mid-1;
  v=tmp;
}else{
  lo=mid+1;
}
 }
cout<<lo<<endl;
//vvl v(n+1);
rep(i,0,n-1){
  for(auto &it:v[i]){
    cout<<it+1<<" ";
  }
  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 53 ms 5244 KB Output is correct
2 Correct 36 ms 5316 KB Output is correct
3 Correct 36 ms 5132 KB Output is correct
4 Correct 51 ms 5244 KB Output is correct
5 Correct 36 ms 5240 KB Output is correct
6 Correct 37 ms 5088 KB Output is correct
7 Correct 34 ms 5364 KB Output is correct
8 Correct 38 ms 5244 KB Output is correct
9 Correct 52 ms 13424 KB Output is correct
10 Correct 44 ms 14328 KB Output is correct
11 Correct 28 ms 4532 KB Output is correct
12 Correct 53 ms 8716 KB Output is correct
13 Correct 80 ms 14152 KB Output is correct
14 Correct 131 ms 19272 KB Output is correct
15 Correct 132 ms 21320 KB Output is correct
16 Correct 188 ms 26124 KB Output is correct
17 Runtime error 225 ms 33760 KB Memory limit exceeded
18 Runtime error 242 ms 34904 KB Memory limit exceeded
19 Runtime error 292 ms 44708 KB Memory limit exceeded
20 Runtime error 237 ms 33764 KB Memory limit exceeded