Submission #1177826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177826		sergio_sak	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	155 ms	131072 KiB

jobs

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bit>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <time.h>
#include <random>
#include <iomanip>
#include <inttypes.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;

template <class T>
using Tree = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3,Ofast")

#define si(n) scanf("%lld", &n);
#define sl(n) scanf("%lld", &n);
#define sc(n) scanf("%c", &n);
#define sf(n) scanf("%f", &n);
#define slf(n) scanf("%lf", &n);

#define fi first
#define se second
// #define int long long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define dbg(x) std::cerr << #x << ": " << x << std::endl;

typedef std::set<int> si;
typedef std::pair<int, int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> dvi;
typedef std::unordered_map<int , int> mi;

const float EPS = 1e-9;
const float PI = acos(-1);
const int MAXN = 1000005;
const int MOD = 1000000007;
const int INF = INT64_MAX;

int gcd(int a, int b) {return (b == 0) ? a : gcd(b, a%b);}
int lcm(int a, int b) {return a/gcd(a, b) * b;}

int N, D, M;
std::pair<int, vi> freq[MAXN];


bool isPossibel(int exMachina) {
    for(int i = 1; i <= N; ++i) {
        if((freq[i].fi+exMachina-1)/exMachina > D) return false;
    }

    return true;
}

signed main()
{
    
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin>>N>>D>>M;

    for(int i = 0; i < M; ++i) {
        int num; std::cin>>num;
        freq[num].fi++;
        freq[num].se.pb(i+1);
    }

    int low = 1, high = 1e6, mid = 0, ans = 0;

    while(low < high) {
        mid = low + (high-low)/2;
        if(isPossibel(mid)) {
            high = mid;
        } else {
            ans = mid+1;
            low = mid+1;
        }
    }

    std::cout<<ans<<"\n";
    for(int i = 1; i <= N; ++i) {
        for(int j = 0; j < ans && j < (int)freq[i].se.size(); ++j) {
            std::cout<<freq[i].se[j]<<" ";
        } std::cout<<0<<"\n";

        for(int j = freq[i].se.size()-1; j >= ans; --j) {
            freq[i+1].se.pb(freq[i].se.back());
            freq[i].se.pop_back();
        }
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp:55:17: warning: overflow in conversion from 'long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   55 | const int INF = INT64_MAX;
      |                 ^~~~~~~~~

• Subtask 1: 0 / 100