답안 #890645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890645 2023-12-21T17:55:40 Z nosaboy Job Scheduling (CEOI12_jobs) C++17
100 / 100
322 ms 23300 KB
#include <bits/stdc++.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using orderedMultiset = tree<T ,null_type,std::less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define f first
#define s second
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i) 
#define all(x) (x).begin(), (x).end()
ll MOD = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

ll add(ll x, ll y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}  
 
ll mult(ll x, ll y)
{
    return (x * 1ll * y) % MOD;
}
ll lpow(ll x, ll y)
{
    if(y == 0){
        return 1;
    }
    ll z = 1;
    while(y)
    {
        if(y & 1) z = mult(z, x);
        x = mult(x, x);
        y >>= 1;
    }
    return z;
}
bool prime(int x)
{
    for(int i = 2; i * 1ll * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;    
}
 
ll inv(ll x) {
	return lpow(x, MOD - 2);
}

ll divide(ll x, ll y)
{
    return mult(x, inv(y));
}
long long gcd(long long int a, long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
 
// Function to return LCM of two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
//math
 
 
vector <ll> ar;
vector <ll> br;
void printDivisors(ll n)
{
    // Note that this loop runs till square root
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i){
                ar.pb(i);
            }
                
  
            else{
                ar.pb(i);
                ar.pb(n/i);
            } // Otherwise print both
                
               
        }
    }
}
void bprintDivisors(ll n)
{
    // Note that this loop runs till square root
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i){
                br.pb(i);
            }
                
  
            else{
                br.pb(i);
                br.pb(n/i);
            } // Otherwise print both
                
               
        }
    }
}
 

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
 
	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
	bool same_set(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return true;
	}
};
/** Computes x^n modulo m in O(log p) time. */
ll qexp(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b % 2) res = res * a % m;
        a = a * a % m;
        b /= 2;
    }
    return res;
}
vector<ll> fact, invf;
 
void precompute(int n) {
    /** Precomputes n! from 0 to MAXN. */
    fact.assign(n + 1, 1); 
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    invf.assign(n + 1, 1);
    /**
    * Precomputes all modular inverse factorials
    * from 0 to MAXN in O(n + log p) time
    */
    invf[n] = qexp(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i > 0; i--) invf[i] = invf[i + 1] * (i + 1) % MOD;
}
/** Computes nCr mod p */
ll nCk(ll n,ll k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
    // return fact[n] * qexp(fact[k], MOD - 2, MOD) % MOD * qexp(fact[n - k], MOD - 2, MOD) % MOD;
}
 


void solve(){
    int n,d,m;cin>>n>>d>>m;
    vector <pi> v;
    rep(i,0,m){
        int u;cin>>u;v.pb({u,i});
    }
    sort(v.begin(),v.end());
    int lo = 0; int hi = 1000000005;
    hi++;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
        int day = 1;
        int cnt = 0;
        bool yn = true;
        rep(i,0,m){
            if(cnt == mid){
                // reset
                day++;
                cnt = 0; 
            }
            if(v[i].first > day){
                day = v[i].first;
                cnt = 0;
            }
            if(day - v[i].first > d){ // past expiration
                yn = false;
            }
            cnt++;
        }
		if (yn) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
    int day = 0;
    int cnt = 0;
    bool yn = true;
    vi aj[n]; // for every day
    rep(i,0,m){
        if(cnt == hi){
            // reset
            day++;
            cnt = 0; 
        }
        if(v[i].first > day){
            day = v[i].first-1; // adjust for 0 indexed
            cnt = 0;
        }
        aj[day].pb(v[i].second);
        cnt++;
    }
    cout<<hi<<endl;
    rep(i,0,n){
        rep(j,0,aj[i].size()){
            cout<<aj[i][j]+1<<" ";
        }
        cout<<0<<endl;
    }
    
}
    


int main(){
	auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;t=1;

    while(t--){
        solve();
    }
  
    
		
 
    
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
   cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
	return 0;
}   

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:17:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
      |                                       ^
jobs.cpp:233:9: note: in expansion of macro 'rep'
  233 |         rep(j,0,aj[i].size()){
      |         ^~~
jobs.cpp:216:10: warning: unused variable 'yn' [-Wunused-variable]
  216 |     bool yn = true;
      |          ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3276 KB Output is correct
2 Correct 28 ms 3288 KB Output is correct
3 Correct 28 ms 3288 KB Output is correct
4 Correct 38 ms 3288 KB Output is correct
5 Correct 34 ms 3280 KB Output is correct
6 Correct 28 ms 3288 KB Output is correct
7 Correct 28 ms 3288 KB Output is correct
8 Correct 28 ms 3288 KB Output is correct
9 Correct 136 ms 5072 KB Output is correct
10 Correct 140 ms 5328 KB Output is correct
11 Correct 25 ms 2608 KB Output is correct
12 Correct 48 ms 4808 KB Output is correct
13 Correct 71 ms 8636 KB Output is correct
14 Correct 114 ms 11408 KB Output is correct
15 Correct 117 ms 11832 KB Output is correct
16 Correct 164 ms 16100 KB Output is correct
17 Correct 203 ms 20156 KB Output is correct
18 Correct 210 ms 19764 KB Output is correct
19 Correct 322 ms 23300 KB Output is correct
20 Correct 215 ms 20196 KB Output is correct