제출 #668018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668018		mahesh_193	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	251 ms	17124 KiB

jobs

// REMEMBERING THE PAST , CAN AVOID REPEAT THE SAME 
#include<bits/stdc++.h>
using namespace std;
 
#define mod 1000000007
#define inf 9000000000000000000
typedef long long ll;
#define f first
#define s second
#define all(x) begin(x), end(x)
 
//pbds
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less_equal<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
 
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
 
ll GCD(ll a,ll b){
    if(b>a){
        swap(a,b);
    }
    if(b==0){
        return a;
    }
    return GCD(b,a%b);
}
 
ll power(ll x,ll y){
    ll res=1;
    while (y){
        if (y & 1){
            res=(res*x)%mod;
        }
        x=(x*x)%mod;
        y=y>>1;
    }
    return res%mod;
}
 
ll add(ll x,ll y){
    return (x+y)%mod;
}
ll sub(ll x,ll y){
    return (x-y+mod)%mod;
} 
ll mul(ll x,ll y){
    return (x*y)%mod;
}
ll divide(ll x,ll y){
    return (x*(power(y,mod-2)))%mod;
}
 
//int const N=2e6+10;
//ll fact[N];
//ll NCR(int n,int r){
//     ll num=fact[n];
//     ll deno=mul(fact[r],fact[n-r]);
//     ll ans=divide(num,deno);
//     return ans;
//}
 
//bool isPrime[N];
//int primeFactor[N];
//vector<int> primes;
//void checkPrime(){
//     memset(isPrime,true,sizeof(isPrime));
//     memset(primeFactor,0,sizeof(primeFactor));
//     int i=2;
//     isPrime[0]=isPrime[1]=false;
//     while(i*i<N){
//         if(isPrime[i]){
//             for(int j=i*i;j<N;j+=i){
//                 isPrime[j]=false;
//                 primeFactor[j]=i;
//             }
//         }
//         i++;
//     }
// 
//     for(int i=2;i<N;i++){
//            if(isPrime[i]){
//                primes.push_back(i);
//            }
//         if(primeFactor[i]==0){
//             primeFactor[i]=i;
//         }
//     }
//}
 
bool checkPalindrome(int l,int r,string &s){
    while(l<r){
        if(s[l]!=s[r]){
            return false;
        }
        l++;
        r--;
    }
    return true;
}
 
//--> base cases 1,2.. ?
//--> BS on answer ?
//--> DP max or min val?
//--> GCD , n^0.5 ?
//--> brute force ?
//--> use long double ?

void solve() {
	int n, d, m, x;
	cin >> n >> d >> m;
	vector<pair<int, int>> jobs(m);
	for (int i = 0; i < m; i++) {
		cin >> x;
		jobs[i] = {x, i + 1};
	}
	sort(all(jobs));
	ll l = 1, r = m, mid, ans;
	while (l <= r) {
		mid = l + (r - l) / 2;
		int i = 1, j = 0, cnt = 0;
		bool flag = true;
		while (j < m) {
			while (j < m && cnt < mid && jobs[j].f <= i) {
				if (i - jobs[j].f > d) {
					flag = false;
					break;
				}
				cnt++;
				j++;
			}
			if (!flag) break;
			i++;
			cnt = 0;
		}
 		if (flag) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << "\n";
	int j = 0, i = 1, cnt = 0;
	while (j < m || i <= n) {
		while (j < m && cnt < ans && jobs[j].f <= i) {
			cnt++;
			cout << jobs[j].s << " ";
			j++;
		}
		cout << "0\n";
		i++;
		cnt = 0;
	}
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //setIO("problemname");
    int t=1;
    // cin>>t;
    //checkPrime();
    //fact[0]=1;
    //for(int i=1;i<N;i++){
        //fact[i]=mul(i,fact[i-1]);
    //}
    for(int T=1;T<=t;T++){
        solve();
    }
    return 0;
}

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

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:19:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | freopen((s + ".in").c_str(), "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:20:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 | freopen((s + ".out").c_str(), "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:122:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |  ll l = 1, r = m, mid, ans;
      |                        ^~~

• Subtask 1: 100 / 100