Submission #409911

#	Time	Username	Problem	Language	Result	Execution time	Memory
409911		Richw818	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	303 ms	17172 KiB

jobs

/*
 *  Written by: Richw818
 *  Lang: C++17
 *  main.cpp
 */
#include <bits/stdc++.h>
using namespace std;
//Macros
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define str string
#define fi first
#define se second
#define REP(i, n) for(int i = 0; i < (int)n; ++i)
#define sz(a) (int)(a.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
//IO
template<class H, class T> void read(pair<H, T> &p);
template<class T> void read(vector<T>& v);
template<class T> void read(T& t){
    cin >> t;
}
template<class H, class... T> void read(H& h, T&... t){
    read(h);
    read(t...);
}
template<class T> void read(vector<T>& v){
    for(auto &t : v)
        read(t);
}
template<class H, class T> void read(pair<H, T> &p){
    read(p.fi, p.se);
}
void setIn(str s){
    freopen(s.c_str(), "r", stdin);
}
void setOut(str s){
    freopen(s.c_str(), "w", stdout);
}
void setIO(str s = ""){
    if(!sz(s))
        return;
    setIn(s+".in");
    setOut(s+".out");
}
//Debug
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template<class H, class... T> void dbg(H& h, T&... t){
    dbg(h);
    dbg(t...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x);
#else
#define dbg(x...)
#endif
//Constants
ll MODS[2] = {1000000007, 998244353};
const ll MOD = MODS[0];
const ll INF = (ll)1e18;
const double PI = acos(-1.0);
const int MAXN = (int)3e5+7;
//Code
int n, d, m;
vector<pair<int,int>> jobs;
bool can(int mach){
    int day = 1, curr = 0;
    for(auto j : jobs){
        if(day > j.fi + d)
            return false;
        if(j.fi > day){
            curr = 0;
            ++day;
            continue;
        }
        ++curr;
        if(curr >= mach){
            ++day;
            curr = 0;
        }
    }
    return true;
}
void solve(){
    read(n, d, m);
    jobs.resize(m);
    REP(i, m){
        read(jobs[i].fi);
        jobs[i].se = i+1;
    }
    sort(all(jobs));
    int l = 1, r = m;
    while(l <= r){
        int mid = (l + r) / 2;
        bool val = can(mid);
        if(val)
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << l << '\n';
    int j = 0;
    for(int i = 1; i <= n; ++i){
        int curr = 0;
        while(j < m && curr < l && jobs[j].fi <= i){
            cout << jobs[j].se << ' ';
            ++curr;
            ++j;
        }
        cout << 0 << '\n';
    }
}
int main(){
    setIO();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

jobs.cpp: In function 'void setIn(std::string)':
jobs.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(s.c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void setOut(std::string)':
jobs.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen(s.c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100