oj.uz

답안 #684575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684575 2023-01-21T19:26:44 Z shalekberli Job Scheduling (CEOI12_jobs) C++17
100 / 100
 330 ms 30640 KB 
/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
Maybe IOI?
*/
  
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e12
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pcc pair<char, char>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define loopch(i, k, n, d) for(char i = (k); i <= (n);i += (d))
#define loopchr(i, k, n, d) for(char i = (k); i >= (n);i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readp(x) for(auto &i : x) cin >> i.F >> i.S;
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define writep(x) for(auto &i: x) cout << i.F << " " << i.S << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;

/* ll pw(ll a, ll b){
    if(b == 0) return 1;
    if(b == 1) return a;
    if(b & 1) return a * pw(a, b - 1);
    return pw((a * a), b / 2);
} */

/* ll pwmod(ll a, ll b, ll m){
    a %= m;
    if(b == 0) return 1;
    if(b == 1) return a;
    if(b & 1) return (a * pwmod(a, b - 1, m)) % m;
    return pwmod((a * a) % m, b / 2, m);
} */

int n, d, m;
vector<int> days;
vector<pii> jobs;
vector<vector<int>> ansjobs;
bool validate(int machines){
    int idx = 0;
    vector<vector<int>> curres(n);
    loop1(day, n, 1){
        loop0(i, machines, 1){
            if(jobs[idx].F > day) break;
            if(jobs[idx].F + d >= day){
                curres[day - 1].pb(jobs[idx++].S);
            }
            else{
                return false;
            }
            if(idx == m){
                ansjobs = curres;
                return true;
            }
        }
    }
    return false;
}

void solve(){
    cin >> n >> d >> m;
    days.resize(m);
    loop0(i, m, 1){
        cin >> days[i];
        jobs.pb({days[i], i + 1});
    }
    sort(all(jobs));
    int l = 1, r = m, ans = m;
    //ans = r;
    while(l <= r){
        int mid = (l + r) / 2;
        if(validate(mid)){
            ans = min(ans, mid);
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << ans << endl;
    loop0(i, n, 1){
        for(auto &to : ansjobs[i]){
            cout << to << " ";
        }
        cout << 0 << endl;
    }
}

void Tour_de_Force(string head_hunter){
    string head_hunter1 = head_hunter + ".in";
    freopen(head_hunter1.c_str() , "r", stdin);
    string head_hunter2 = head_hunter + ".out";
    freopen(head_hunter2.c_str() , "w", stdout);
}

int main(){
    need_for_speed
    //Tour_de_Force("sabotage");
    solve();
    /* ll t; cin >> t;
    while(t--){
        solve();
    } */
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message

jobs.cpp: In function 'void Tour_de_Force(std::string)':
jobs.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen(head_hunter1.c_str() , "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     freopen(head_hunter2.c_str() , "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3748 KB Output is correct
2 Correct 26 ms 3572 KB Output is correct
3 Correct 25 ms 3656 KB Output is correct
4 Correct 25 ms 3664 KB Output is correct
5 Correct 27 ms 3612 KB Output is correct
6 Correct 25 ms 3664 KB Output is correct
7 Correct 26 ms 3724 KB Output is correct
8 Correct 26 ms 3704 KB Output is correct
9 Correct 48 ms 8084 KB Output is correct
10 Correct 46 ms 8228 KB Output is correct
11 Correct 34 ms 3160 KB Output is correct
12 Correct 79 ms 6156 KB Output is correct
13 Correct 104 ms 9572 KB Output is correct
14 Correct 160 ms 13188 KB Output is correct
15 Correct 167 ms 14744 KB Output is correct
16 Correct 226 ms 18148 KB Output is correct
17 Correct 285 ms 22832 KB Output is correct
18 Correct 280 ms 23824 KB Output is correct
19 Correct 330 ms 30640 KB Output is correct
20 Correct 283 ms 22776 KB Output is correct