제출 #890641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890641		nosaboy	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	334 ms	20176 KiB

jobs

#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; 
        }
        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;
}   

컴파일 시 표준 에러 (stderr) 메시지

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:229:9: note: in expansion of macro 'rep'
  229 |         rep(j,0,aj[i].size()){
      |         ^~~
jobs.cpp:216:10: warning: unused variable 'yn' [-Wunused-variable]
  216 |     bool yn = true;
      |          ^~

• Subtask 1: 100 / 100