oj.uz

답안 #668018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668018 2022-12-02T14:46:28 Z mahesh_193 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 251 ms 17124 KB 
// 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;
}

Compilation message

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1988 KB Output is correct
2 Correct 19 ms 1996 KB Output is correct
3 Correct 17 ms 1972 KB Output is correct
4 Correct 35 ms 1996 KB Output is correct
5 Correct 17 ms 1972 KB Output is correct
6 Correct 18 ms 1996 KB Output is correct
7 Correct 23 ms 1972 KB Output is correct
8 Correct 18 ms 2008 KB Output is correct
9 Correct 27 ms 2124 KB Output is correct
10 Correct 28 ms 2124 KB Output is correct
11 Correct 24 ms 1992 KB Output is correct
12 Correct 50 ms 3912 KB Output is correct
13 Correct 73 ms 5800 KB Output is correct
14 Correct 123 ms 8040 KB Output is correct
15 Correct 127 ms 9460 KB Output is correct
16 Correct 161 ms 11904 KB Output is correct
17 Correct 185 ms 13876 KB Output is correct
18 Correct 220 ms 15036 KB Output is correct
19 Correct 251 ms 17124 KB Output is correct
20 Correct 194 ms 13972 KB Output is correct