oj.uz

Submission #591338

# Submission time Handle Problem Language Result Execution time Memory
591338 2022-07-07T10:19:32 Z YassineBenYounes Job Scheduling (CEOI12_jobs) C++17
100 / 100
 247 ms 13824 KB 
/*
ID: Yassine BenYounes
TASK: maxcross
LANG: C++                 
*/
#include<bits/stdc++.h>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
ll modd(ll x, ll n){while(x < 0){x += n;}return (x % n);} // modulo for negative numbers
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
 
const int mx = 2*1e5 + 9;
const ll mod = 1e9+7;
const ll inf = 1e15;
int n;int d;int m;

vii v;

bool f(int t){
    int day = 1;
    for(int i = 1; i <= m;){
        int c = 0;
        while(i <= m && c < t && day >= v[i].ff){
            if(day - v[i].ff > d)return 0;
            i++;c++;
        }
        day++;
    }
    return 1;
}

int solve(){
    int low = 1;
    int high = 1e9 + 9;
    int ans = 1;
    while(low <= high){
        ll mid = low + (high - low) / 2;
        if(f(mid)){
            ans = mid;
            high = mid-1;
        }
        else{
            low = mid+1;
        }
    }
    return ans;
}

int main(){
    speed;
    cin >> n >> d >> m;
    v.pb({0, 0});
    for(int i = 0; i < m;i++){
        int x;cin >> x;
        v.pb({x, i+1});
    }
    sort(all(v));
    int x = solve();
    cout << x << endl;
    int c = 0;
    for(int i = 1; i <= m;i++){
        cout << v[i].ss << " ";
        if(i % x == 0){c++;cout << "0" << endl;}
    }
    for(int i = 0; i < n-c;i++){
        cout << "0" << endl;
    }
}
 
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
*/

Compilation message

jobs.cpp: In function 'void init()':
jobs.cpp:34:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:36:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1744 KB Output is correct
2 Correct 19 ms 1836 KB Output is correct
3 Correct 24 ms 1764 KB Output is correct
4 Correct 20 ms 1736 KB Output is correct
5 Correct 20 ms 1872 KB Output is correct
6 Correct 18 ms 1744 KB Output is correct
7 Correct 19 ms 1836 KB Output is correct
8 Correct 18 ms 1760 KB Output is correct
9 Correct 28 ms 1936 KB Output is correct
10 Correct 31 ms 2016 KB Output is correct
11 Correct 31 ms 1744 KB Output is correct
12 Correct 50 ms 3304 KB Output is correct
13 Correct 79 ms 4788 KB Output is correct
14 Correct 137 ms 6224 KB Output is correct
15 Correct 127 ms 7792 KB Output is correct
16 Correct 159 ms 9208 KB Output is correct
17 Correct 189 ms 10704 KB Output is correct
18 Correct 219 ms 12204 KB Output is correct
19 Correct 247 ms 13824 KB Output is correct
20 Correct 186 ms 10668 KB Output is correct