oj.uz

답안 #1109019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109019 2024-11-05T18:57:18 Z yazansh Job Scheduling (CEOI12_jobs) C++17
80 / 100
 610 ms 47288 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";

 function<pair<bool,vvl>(ll)>check=[&](ll r)->pair<bool,vvl>{
 vvl  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,tmp};
}else{
  tmp[i-1].em(a[cnt].ss);
  cnt++;
}
if(cnt>=m)return {1,tmp};
  }

}
return {0,tmp};

 };
 vvl v(n);
 ll lo=1,hi=1e9;
 ll ans=m;
 while(lo<=hi){
  ll mid= lo + (hi-lo)/2;
  pair<bool,vvl>p=check(mid);
if(p.ff){
  hi=mid-1;
  ans=mid;
  v=p.ss;
}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

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 6528 KB Output is correct
2 Correct 59 ms 6540 KB Output is correct
3 Correct 56 ms 6560 KB Output is correct
4 Correct 78 ms 6580 KB Output is correct
5 Correct 52 ms 6584 KB Output is correct
6 Correct 69 ms 6528 KB Output is correct
7 Correct 58 ms 6572 KB Output is correct
8 Correct 54 ms 6604 KB Output is correct
9 Correct 155 ms 11640 KB Output is correct
10 Correct 166 ms 11740 KB Output is correct
11 Correct 62 ms 4964 KB Output is correct
12 Correct 121 ms 9024 KB Output is correct
13 Correct 174 ms 14636 KB Output is correct
14 Correct 260 ms 19616 KB Output is correct
15 Correct 275 ms 23620 KB Output is correct
16 Correct 352 ms 29576 KB Output is correct
17 Runtime error 433 ms 34244 KB Memory limit exceeded
18 Runtime error 488 ms 35844 KB Memory limit exceeded
19 Runtime error 610 ms 47288 KB Memory limit exceeded
20 Runtime error 415 ms 34372 KB Memory limit exceeded