oj.uz

Submission #905049

# Submission time Handle Problem Language Result Execution time Memory
905049 2024-01-12T13:27:06 Z akliu Job Scheduling (CEOI12_jobs) C++11
100 / 100
 291 ms 20164 KB 
#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 inevitable since we want to preserve the order of the size of each machine
    deque<int> q; // However, 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);
    multiset<pii> machines;
    deque<pii> 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;
            pii valQ = *(q.begin());
            machines.ins(mp(valQ.fi, valQ.se));
            q.pop_front();
        }
        while (val.day == d) {
            val = *it;
            if (machines.sz() != l) {
                machines.ins(mp(val.day, val.n));
            }
            else q.push_back(mp(val.day, val.n));
            ++it;
            if (it == v.end()) break;
        }
        for (auto &x : machines) {
            ans[d].pb(x.se);
        }
        ++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

jobs.cpp: In function 'void solve()':
jobs.cpp:109:30: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, 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::multiset<std::pair<int, 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5068 KB Output is correct
2 Correct 41 ms 5068 KB Output is correct
3 Correct 32 ms 5080 KB Output is correct
4 Correct 33 ms 5088 KB Output is correct
5 Correct 32 ms 5324 KB Output is correct
6 Correct 33 ms 5328 KB Output is correct
7 Correct 33 ms 5244 KB Output is correct
8 Correct 35 ms 5192 KB Output is correct
9 Correct 37 ms 5064 KB Output is correct
10 Correct 39 ms 5072 KB Output is correct
11 Correct 30 ms 2252 KB Output is correct
12 Correct 72 ms 4452 KB Output is correct
13 Correct 90 ms 6652 KB Output is correct
14 Correct 136 ms 9348 KB Output is correct
15 Correct 154 ms 9620 KB Output is correct
16 Correct 180 ms 13236 KB Output is correct
17 Correct 219 ms 16648 KB Output is correct
18 Correct 257 ms 18284 KB Output is correct
19 Correct 291 ms 20164 KB Output is correct
20 Correct 225 ms 17804 KB Output is correct