Submission #493803

#	Time	Username	Problem	Language	Result	Execution time	Memory
493803		viethoangpham	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	509 ms	45352 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
#define mp make_pair
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(200005);
vector <vector <ll>> res;
pair <bool, vector <vector<ll>>> ok(const vector <pair<ll, ll>> &a, ll mac_cnt){
    vector <vector <ll>> schedule(n);
    ll mac_cur = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < mac_cnt; 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 mp(false, schedule);
            if (mac_cur == m) return mp(true, schedule);
        }
    }
    return mp(false, schedule);
}
main(){
//    setIO("Codeforces");
    faster
    cin >> n >> d >> m;
    a.resize(m);
    for (int i = 0; i < m; i++){
        ll x; cin >> x;
        a[i] = mp(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 u : res[i]){
            cout << u << " ";
        }
        cout << 0 << el;
    }
}

Compilation message (stderr)

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

• Subtask 1: 80 / 100