Submission #890630

# Submission time Handle Problem Language Result Execution time Memory
890630 2023-12-21T17:12:01 Z nosaboy Job Scheduling (CEOI12_jobs) C++17
55 / 100
313 ms 20632 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(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;
}   

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:225:9: note: in expansion of macro 'rep'
  225 |         rep(j,0,aj[i].size()){
      |         ^~~
jobs.cpp:212:10: warning: unused variable 'yn' [-Wunused-variable]
  212 |     bool yn = true;
      |          ^~
# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2672 KB Output isn't correct
2 Incorrect 30 ms 2520 KB Output isn't correct
3 Incorrect 27 ms 2412 KB Output isn't correct
4 Incorrect 29 ms 2516 KB Output isn't correct
5 Incorrect 32 ms 2260 KB Output isn't correct
6 Incorrect 26 ms 2516 KB Output isn't correct
7 Incorrect 32 ms 2604 KB Output isn't correct
8 Incorrect 30 ms 2848 KB Output isn't correct
9 Correct 131 ms 4776 KB Output is correct
10 Correct 131 ms 4724 KB Output is correct
11 Correct 25 ms 2264 KB Output is correct
12 Correct 45 ms 4296 KB Output is correct
13 Correct 69 ms 6844 KB Output is correct
14 Correct 104 ms 9148 KB Output is correct
15 Incorrect 112 ms 9660 KB Output isn't correct
16 Correct 149 ms 12128 KB Output is correct
17 Correct 174 ms 17608 KB Output is correct
18 Correct 200 ms 17604 KB Output is correct
19 Correct 313 ms 20632 KB Output is correct
20 Correct 173 ms 16700 KB Output is correct