oj.uz

Submission #1109007

# Submission time Handle Problem Language Result Execution time Memory
1109007 2024-11-05T18:44:51 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 289 ms 44720 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(n);
 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 32 ms 5348 KB Output is correct
2 Correct 31 ms 5092 KB Output is correct
3 Correct 32 ms 5348 KB Output is correct
4 Correct 38 ms 5268 KB Output is correct
5 Correct 34 ms 5348 KB Output is correct
6 Correct 31 ms 5248 KB Output is correct
7 Correct 31 ms 5092 KB Output is correct
8 Correct 32 ms 5092 KB Output is correct
9 Correct 48 ms 13416 KB Output is correct
10 Correct 41 ms 14224 KB Output is correct
11 Correct 28 ms 4688 KB Output is correct
12 Correct 54 ms 8716 KB Output is correct
13 Correct 77 ms 14108 KB Output is correct
14 Correct 122 ms 19264 KB Output is correct
15 Correct 126 ms 21320 KB Output is correct
16 Correct 178 ms 26084 KB Output is correct
17 Runtime error 218 ms 33740 KB Memory limit exceeded
18 Runtime error 218 ms 35000 KB Memory limit exceeded
19 Runtime error 289 ms 44720 KB Memory limit exceeded
20 Runtime error 224 ms 33788 KB Memory limit exceeded