oj.uz

답안 #705282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705282 2023-03-03T18:47:35 Z Huseyn123 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 297 ms 27780 KB 
#include <bits/stdc++.h>
#define MAX 1000001
#define INF 2e9
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
vector<pll> v1;
bool f(ll x){
    ll j=0;
    for(int i=1;i<=n;i++){
        ll h=min(k,j+x);
        while(j<h){
            if(a[j]>i){
                break;
            }
            if(i>a[j]+m){
                return false;
            }
            j++;
        }
    }
    if(j<k){
        return false;
    }
    return true;
}
void solve(){
    cin >> n >> m >> k;
    v1.resize(k);
    for(int i=0;i<k;i++){
        cin >> a[i];
        v1[i]=mp(a[i],i+1);
    }
    sort(a,a+k);
    sortv(v1);
    ll l=0,r=k;
    while(l<r){
        ll mid=(l+r)/2;
        if(f(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout << r << "\n";
    ll j=0;
    for(int i=1;i<=n;i++){
        ll h=min(k,j+r);
        while(j<h){
            if(a[j]>i){
                break;
            }
            cout << v1[j].ss << " ";
            j++;
        }
        cout << 0 << "\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //USACO("angry");
    //freopen("input.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++;
    }
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 3284 KB Output is correct
2 Correct 18 ms 3200 KB Output is correct
3 Correct 26 ms 3200 KB Output is correct
4 Correct 19 ms 3188 KB Output is correct
5 Correct 17 ms 3284 KB Output is correct
6 Correct 18 ms 3284 KB Output is correct
7 Correct 18 ms 3232 KB Output is correct
8 Correct 25 ms 3244 KB Output is correct
9 Correct 36 ms 3440 KB Output is correct
10 Correct 32 ms 3440 KB Output is correct
11 Correct 28 ms 3232 KB Output is correct
12 Correct 67 ms 6304 KB Output is correct
13 Correct 84 ms 9288 KB Output is correct
14 Correct 120 ms 12408 KB Output is correct
15 Correct 145 ms 15392 KB Output is correct
16 Correct 185 ms 18468 KB Output is correct
17 Correct 234 ms 21608 KB Output is correct
18 Correct 226 ms 24620 KB Output is correct
19 Correct 297 ms 27780 KB Output is correct
20 Correct 232 ms 21536 KB Output is correct