Submission #905055

#	Time	Username	Problem	Language	Result	Execution time	Memory
905055		akliu	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	257 ms	21240 KiB

jobs

#include <bits/stdc++.h>
 
using namespace std;
 
void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
 
void open(string filename) {
    fastio();
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
typedef long long ll;
#define vll vector<ll>
#define vint vector<int>
#define vbool vector<bool>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define ins(x) insert(x)
#define sz() size()
#define lb() lower_bound()
#define ub() upper_bound()
#define rsz resize
#define se second
#define fi first
#define cont continue
 
// scary demonic thing
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
struct g {
    int day, n;
    bool operator<(const g &y) {
        if (day != y.day) return day < y.day;
        return n < y.n; // Not necessary, compiler gives annoying error otherwise though
    }
};
 
int N, D, M;
vector<g> v;
 
bool check(int m) {
    // Iterate to check if the minimum is valid
    int machines; // Using a multiset for machines is not necessary here because for the binary search we don't care about the values that we're storing. All we care about are the number of machines that are being used each day.
    deque<int> q; // Note that q does NOT need to be sorted because we're pushing elements into q in chronological order. Therefore, the elements at the front of q will always be the ones that we need to check for the date limit violation. 
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        if (q.sz()) {
            if (d - *(q.begin()) > D) {
                return false;
            }
        }
        machines = 0;
        val = *it;
        while (machines != m) {
            if (!q.sz()) break;
            ++machines;
            q.pop_front();
        }
        while (val.day == d) {
            if (machines != m) ++machines;
            else q.push_back(val.day);
            ++it;
            if (it == v.end()) break;
            val = *it;
        }
        ++d;
    }
    return true;
}
 
void solve() {
    // Input
    cin >> N >> D >> M;
    for (int i = 0; i < M; ++i) {
        int a; cin >> a;
        v.pb({a, i + 1});
    }
    sort(v.begin(), v.end());
 
    // Binary search
    int l = 1, r = 1e6, m;
    while (l < r) {
        m = (l + r) / 2;
        if (check(m)) r = m;
        else l = m + 1;
    }
    cout << l << "\n";
 
    // Iterate once more with the correct minimum, very minor changes to the binary search algorithm to allow for storing the index of the value
    vector<vint> ans(N + 1);
    vector<int> machines;
    deque<int> q;
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        machines.clear();
        val = *it;
        while (machines.sz() != l) {
            if (!q.sz()) break;
            int valQ = *(q.begin());
            machines.pb(valQ);
            q.pop_front();
        }
        while (val.day == d) {
            val = *it;
            if (machines.sz() != l) {
                machines.pb(val.n);
            }
            else q.push_back(val.n);
            ++it;
            if (it == v.end()) break;
        }
        for (auto &x : machines) {
            ans[d].pb(x);
        }
        ++d;
    }
 
    // Output
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < ans[i].sz(); ++j) {
            cout << ans[i][j] << " ";
        }
        cout << "0\n";
    }
}
 
int main() {
    fastio();
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
 
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:109:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |         while (machines.sz() != l) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:117:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int j = 0; j < ans[i].sz(); ++j) {
      |                           ^
jobs.cpp: In function 'void open(std::string)':
jobs.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100