Submission #684503

#	Time	Username	Problem	Language	Result	Execution time	Memory
684503		shalekberli	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	526 ms	65536 KiB

jobs

/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
Maybe IOI?
*/
  
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e12
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pcc pair<char, char>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define loopch(i, k, n, d) for(char i = (k); i <= (n);i += (d))
#define loopchr(i, k, n, d) for(char i = (k); i >= (n);i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readp(x) for(auto &i : x) cin >> i.F >> i.S;
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define writep(x) for(auto &i: x) cout << i.F << " " << i.S << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;

/* ll pw(ll a, ll b){
    if(b == 0) return 1;
    if(b == 1) return a;
    if(b & 1) return a * pw(a, b - 1);
    return pw((a * a), b / 2);
} */

/* ll pwmod(ll a, ll b, ll m){
    a %= m;
    if(b == 0) return 1;
    if(b == 1) return a;
    if(b & 1) return (a * pwmod(a, b - 1, m)) % m;
    return pwmod((a * a) % m, b / 2, m);
} */

int n, d, m;
vector<int> days;
map<int, vector<int>> jobs, tmp, ansjobs;

bool validate(int machines){
    tmp = jobs;
    for(auto &to : tmp){
        if(sz(to.S) <= machines){
            continue;
        }
        int idx = 0;
        while(sz(to.S) - idx > machines){
            if(to.F + 1 >= n) return false;
            tmp[to.F + 1].pb(to.S[idx]);
            to.S[idx] = -1;
            idx++;
        }
    }
    return true;
}

void solve(){
    cin >> n >> d >> m;
    days.resize(m);
    loop0(i, m, 1){
        cin >> days[i];
        jobs[days[i]].pb(i);
    }
    int l = 1, r = m, ans = m;
    //ans = r;
    while(l <= r){
        int mid = (l + r) / 2;
        if(validate(mid)){
            ans = min(ans, mid);
            r = mid - 1;
            ansjobs = tmp;
        }
        else{
            l = mid + 1;
        }
    }
    cout << ans << endl;
    loop1(i, n, 1){
        for(auto &to : ansjobs[i]){
            if(to != -1) cout << to + 1 << " ";
        }
        cout << 0 << endl;
    }
}

void Tour_de_Force(string head_hunter){
    string head_hunter1 = head_hunter + ".in";
    freopen(head_hunter1.c_str() , "r", stdin);
    string head_hunter2 = head_hunter + ".out";
    freopen(head_hunter2.c_str() , "w", stdout);
}

int main(){
    need_for_speed
    //Tour_de_Force("sabotage");
    solve();
    /* ll t; cin >> t;
    while(t--){
        solve();
    } */
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

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

• Subtask 1: 10 / 100