Submission #525682

#	Time	Username	Problem	Language	Result	Execution time	Memory
525682		ddaftari	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	812 ms	30552 KiB

jobs

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

//template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find_by_order, order_of_key
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define inf 1e18
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define iter(n) for (auto &el : n)
#define rep(i, init, n) for (ll i = init; i < (ll)n; i++)
#define rev(i, n, init) for (ll i = (ll)n; i >= init; i--)
#define V vector<int>
#define VV vector<V>
#define Vll vector<ll>
#define VVll vector<Vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define Vpii vector<pii>
#define Vpll vector<pll>
#define Mpll map<ll,ll>
void fileIO(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
void fileIN(string filename) {freopen((filename).c_str(), "r", stdin);}
void fileOUT(string filename) {freopen((filename).c_str(), "w", stdout);}
bool comparator(pair<ll, ll> a, pair<ll, ll> b){ // Ascending First
    return a.ff < b.ff;
}

// 48-57 -> 0-9
// 65-90 -> A-Z
// 97-122 -> a-z

bool check(Mpll m, ll n, ll d, ll machines){
    if(machines == 0) return false;
    ll prev = 0;
    rep(i,1,n-d+1){
        if(prev/machines + m[i]/machines - 1 <= d){
            prev = prev - machines + m[i];
        }else return false;
    }
    return true;
}

void solve()
{
    ll n,d,m;
    cin>>n>>d>>m;
    Mpll mp;
    Vpll v(m);
    ll x,y;
    rep(i,0,m){
        cin>>x;
        v[i] = {x,i+1};
        mp[x]++;
    }
    ll l = 0;
    ll r = 2*m;
    ll ans = 0;
    while(l<=r){
        ll mid = l + (r-l)/2;
        if(check(mp,n,d,mid)){
            ans = mid;
            // cout<<mid<<endl;
            r = mid - 1;
        }else l = mid + 1;
    }
    cout<<ans<<endl;
    sort(all(v));
    ll div;
    if(m%ans == 0){
        div = m/ans;
    }else{
        div = m/ans + 1;
    }
    ll ind = 0;
    rep(i,0,div){
        ll j = 0;
        while(j<ans && ind<sz(v)){
            cout<<v[ind].ss<<" ";
            j++;
            ind++;
        }
        cout<<0<<endl;
    }
    rep(i,0,n-div){
        cout<<0<<endl;
    }
return;
}

int main()
{
    fastio
    //fileIO("");
    //fileIN("");
    //fileOUT("");
    ll tc = 1;
    //cin>>tc;
    while(tc--){
        solve();
    }
return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:62:10: warning: unused variable 'y' [-Wunused-variable]
   62 |     ll x,y;
      |          ^
jobs.cpp: In function 'void fileIO(std::string)':
jobs.cpp:32:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 | freopen((filename + ".in").c_str(), "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:33:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | freopen((filename + ".out").c_str(), "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void fileIN(std::string)':
jobs.cpp:35:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void fileIN(string filename) {freopen((filename).c_str(), "r", stdin);}
      |                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void fileOUT(std::string)':
jobs.cpp:36:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 | void fileOUT(string filename) {freopen((filename).c_str(), "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 100