Submission #525950

# Submission time Handle Problem Language Result Execution time Memory
525950 2022-02-13T09:45:42 Z ddaftari Job Scheduling (CEOI12_jobs) C++17
15 / 100
813 ms 27136 KB
#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+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

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);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 3112 KB Output isn't correct
2 Incorrect 45 ms 3104 KB Output isn't correct
3 Incorrect 54 ms 2992 KB Output isn't correct
4 Incorrect 48 ms 3012 KB Output isn't correct
5 Incorrect 46 ms 3012 KB Output isn't correct
6 Incorrect 53 ms 3016 KB Output isn't correct
7 Incorrect 46 ms 3024 KB Output isn't correct
8 Incorrect 52 ms 3000 KB Output isn't correct
9 Incorrect 426 ms 8900 KB Output isn't correct
10 Incorrect 442 ms 8912 KB Output isn't correct
11 Incorrect 30 ms 2500 KB Output isn't correct
12 Correct 65 ms 4880 KB Output is correct
13 Incorrect 90 ms 7108 KB Output isn't correct
14 Correct 175 ms 10456 KB Output is correct
15 Incorrect 154 ms 11588 KB Output isn't correct
16 Correct 241 ms 15064 KB Output is correct
17 Incorrect 289 ms 17272 KB Output isn't correct
18 Incorrect 272 ms 19052 KB Output isn't correct
19 Incorrect 813 ms 27136 KB Output isn't correct
20 Incorrect 277 ms 17268 KB Output isn't correct