Submission #705282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
705282	2023-03-03T18:47:35 Z	Huseyn123	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	297 ms	27780 KB

jobs

#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

#	Verdict	Execution time	Memory	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