oj.uz

Submission #905032

# Submission time Handle Problem Language Result Execution time Memory
905032 2024-01-12T13:11:04 Z akliu Job Scheduling (CEOI12_jobs) C++11
90 / 100
 1000 ms 17584 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")


struct g {
    int day, n;
    bool operator<(const g &y) {
        if (day != y.day) return day < y.day;
        return n < y.n;
    }
};
 
int N, D, M;
vector<g> v;
 
bool check(int m) {
    // Iterate to check if the minimum is valid
    multiset<int> machines;
    multiset<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.erase(q.begin());
        }
        while (val.day == d) {
            if (machines.sz() != m) machines.ins(val.day);
            else q.ins(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;
    multiset<pii> q;
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        machines.clear();
        val = *it;
        while (machines.sz() != l && q.sz()) {
            pii valQ = *(q.begin());
            machines.ins(mp(valQ.fi, valQ.se));
            q.erase(q.begin());
        }
        while (val.day == d) {
            val = *it;
            if (machines.sz() != l) {
                machines.ins(mp(val.day, val.n));
            }
            else q.ins(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:64:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         while (machines.sz() != m) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:70:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
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 && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 7124 KB Output is correct
2 Correct 316 ms 7204 KB Output is correct
3 Correct 293 ms 7212 KB Output is correct
4 Correct 315 ms 7208 KB Output is correct
5 Correct 288 ms 7204 KB Output is correct
6 Correct 296 ms 7212 KB Output is correct
7 Correct 295 ms 7212 KB Output is correct
8 Correct 327 ms 7368 KB Output is correct
9 Correct 147 ms 5284 KB Output is correct
10 Correct 187 ms 5324 KB Output is correct
11 Correct 105 ms 2368 KB Output is correct
12 Correct 323 ms 5112 KB Output is correct
13 Correct 362 ms 6824 KB Output is correct
14 Correct 524 ms 10688 KB Output is correct
15 Correct 503 ms 9616 KB Output is correct
16 Correct 503 ms 13476 KB Output is correct
17 Correct 751 ms 17584 KB Output is correct
18 Execution timed out 1062 ms 9424 KB Time limit exceeded
19 Execution timed out 1008 ms 12764 KB Time limit exceeded
20 Correct 729 ms 16728 KB Output is correct