oj.uz

Submission #905042

# Submission time Handle Problem Language Result Execution time Memory
905042 2024-01-12T13:20:54 Z akliu Job Scheduling (CEOI12_jobs) C++11
100 / 100
 884 ms 20168 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;
    }
};
 
int N, D, M;
vector<g> v;
 
bool check(int m) {
    // Iterate to check if the minimum is valid
    multiset<int> machines;
    deque<int> q;
    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.clear();
        val = *it;
        while (machines.sz() != m) {
            if (!q.sz()) break;
            machines.ins(*(q.begin()));
            q.pop_front();
        }
        while (val.day == d) {
            if (machines.sz() != m) machines.ins(val.day);
            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
    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 'bool check(int)':
jobs.cpp:63:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         while (machines.sz() != m) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:69:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:108: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]
  108 |         while (machines.sz() != l) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:116: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]
  116 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In member function 'bool g::operator<(const g&)':
jobs.cpp:42:5: warning: control reaches end of non-void function [-Wreturn-type]
   42 |     }
      |     ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 6480 KB Output is correct
2 Correct 211 ms 6464 KB Output is correct
3 Correct 200 ms 6336 KB Output is correct
4 Correct 193 ms 6392 KB Output is correct
5 Correct 206 ms 6352 KB Output is correct
6 Correct 209 ms 6456 KB Output is correct
7 Correct 200 ms 6460 KB Output is correct
8 Correct 201 ms 6452 KB Output is correct
9 Correct 123 ms 5076 KB Output is correct
10 Correct 144 ms 5080 KB Output is correct
11 Correct 80 ms 2148 KB Output is correct
12 Correct 187 ms 4448 KB Output is correct
13 Correct 276 ms 7436 KB Output is correct
14 Correct 343 ms 9664 KB Output is correct
15 Correct 495 ms 9664 KB Output is correct
16 Correct 443 ms 13632 KB Output is correct
17 Correct 621 ms 16308 KB Output is correct
18 Correct 808 ms 17076 KB Output is correct
19 Correct 884 ms 20168 KB Output is correct
20 Correct 616 ms 17340 KB Output is correct