oj.uz

답안 #720244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720244 2023-04-07T17:41:32 Z nihaddhuseynli Job Scheduling (CEOI12_jobs) C++14
100 / 100
 294 ms 31020 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 18 ms 3532 KB Output is correct
2 Correct 19 ms 3572 KB Output is correct
3 Correct 22 ms 3504 KB Output is correct
4 Correct 23 ms 3540 KB Output is correct
5 Correct 23 ms 3532 KB Output is correct
6 Correct 18 ms 3500 KB Output is correct
7 Correct 19 ms 3528 KB Output is correct
8 Correct 21 ms 3484 KB Output is correct
9 Correct 33 ms 3712 KB Output is correct
10 Correct 36 ms 3664 KB Output is correct
11 Correct 32 ms 3588 KB Output is correct
12 Correct 65 ms 6988 KB Output is correct
13 Correct 93 ms 10352 KB Output is correct
14 Correct 144 ms 14156 KB Output is correct
15 Correct 163 ms 17228 KB Output is correct
16 Correct 201 ms 21196 KB Output is correct
17 Correct 259 ms 24792 KB Output is correct
18 Correct 255 ms 27440 KB Output is correct
19 Correct 294 ms 31020 KB Output is correct
20 Correct 243 ms 24688 KB Output is correct