Submission #493791

#	Time	Username	Problem	Language	Result	Execution time	Memory
493791		viethoangpham	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	598 ms	45412 KiB

jobs

#include<bits/stdc++.h>
#define faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define el "\n"
#define memset(a, x) memset(a, (x), sizeof(a));
#define sz(x) x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
const int INF = int(1e9) + 100;
const ll MAXN = (1 << 20) + 55;
const ll MOD = 1e6 + 3;
#define yes cout << "yes" << el;
#define no cout << "no" << el;
ll gcd(ll x, ll y){
    return !y?x:gcd(y,x%y);
}
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s) {
	setIn(s+".in"); setOut(s+".out");
}
ll n, d, m;
vector <pair<ll ,ll>> a;
vector <vector<ll>> res;
pair<bool, vector<vector<ll>>> ok (const vector <pair<ll, ll>> &a, ll machine){
    vector <vector <ll>> schedule(n);
    ll mac_cur = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < machine; j++){
            if (a[mac_cur].f > i) break;
            if (a[mac_cur].f + d >= i){
                schedule[i - 1].pb(a[mac_cur].s);
                mac_cur++;
            }else return make_pair(false, schedule);
            if (mac_cur == m){
                return make_pair(true, schedule);
            }
        }
    }
    return make_pair(false, schedule);
}
main(){
//    setIO("Codeforces");
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++){
        ll x; cin >> x;
        a.pb(make_pair(x, i + 1));
    }
    sort(all(a));
    ll l = 0, r = m;
    while (l + 1 < r){
        ll m = l + (r - l) / 2;
        pair <bool, vector<vector<ll>>> check = ok (a, m);
        if (check.f){
            r = m;
            res = check.s;
        }else l = m;
    }
    cout << r << el;
    for (int i = 0; i < n; i++){
        for (auto cur : res[i]){
            cout << cur << " ";
        }
            cout << 0 << el;
    }
}

Compilation message (stderr)

jobs.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~
jobs.cpp: In function 'void setIn(str)':
jobs.cpp:22:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void setOut(str)':
jobs.cpp:23:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100