답안 #891174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891174 2023-12-22T10:00:31 Z Vedant_05 Job Scheduling (CEOI12_jobs) C++17
55 / 100
171 ms 23520 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define pb(a) push_back(a)
#define pbr(a,b) pb(make_pair(a,b))
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define F first
#define S second

ll M = 1e9 + 7;                 //998244353;
const int N = 100001;

ll binpow(ll a, ll b){    ll ans = 1;    while(b > 0){        if(b&1)     ans = (ans * a) % M;        a = (a*a) % M;        b >>= 1;    }    return ans;     }
bool sS(pi p1, pi p2){    return (p1.S < p2.S);     }
bool sF(pi p1, pi p2){    return (p1.F < p2.F);     }

bool chk(int mid, int n, int m, queue<int> q, int a[]){
    fr(i, 1, n){
        fr(j, 0, mid-1){
            if(q.empty())
                break;
            int u = q.front();  q.pop();
            // cout << u << " " << a[u] << ' ' << i << " : ";
            if(a[u] < i)
                return 0;
        }
    }
    if(q.empty())
        return 1;
    return 0;
}

void solve()
{
    int n, d, m;
    cin >> n >> d >> m;
    vector<vi> vec(n-d+1);
    int a[m+1];
    fr(i, 1, m){
        cin >> a[i];
        vec[a[i]].pb(i);
        a[i] += d;
    }
    queue<int> q;
    fr(i, 1, n-d){
        for(auto u: vec[i])
            q.push(u);
    }
    int l = 0, r = m;
    while(r > l+1){
        // cout << l << " " << r << "\n";
        int mid = (l+r) / 2;
        if(chk(mid, n, m, q, a))
            r = mid;
        else
            l = mid;
        // cout << "\n";
    }
    
    cout << r << "\n";
    fr(i, 1, n){
        fr(j, 0, r-1){
            if(q.empty())
                break;
            int u = q.front();  q.pop();
            cout << u << " ";
        }
        cout << "0\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    
    int t=1;
    // cin >> t;
    for(int i = 1; i <= t; i++)
    {
        // cout << "t: " << t << "\n";
        solve();
    }
    return 0;
}




# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 3036 KB Output isn't correct
2 Incorrect 16 ms 3036 KB Output isn't correct
3 Incorrect 16 ms 3036 KB Output isn't correct
4 Incorrect 16 ms 3192 KB Output isn't correct
5 Incorrect 14 ms 3036 KB Output isn't correct
6 Incorrect 15 ms 3420 KB Output isn't correct
7 Incorrect 15 ms 3036 KB Output isn't correct
8 Incorrect 14 ms 3132 KB Output isn't correct
9 Correct 21 ms 5408 KB Output is correct
10 Correct 20 ms 5188 KB Output is correct
11 Correct 19 ms 2896 KB Output is correct
12 Correct 33 ms 5184 KB Output is correct
13 Correct 51 ms 8052 KB Output is correct
14 Correct 76 ms 11032 KB Output is correct
15 Incorrect 84 ms 12304 KB Output isn't correct
16 Correct 122 ms 16360 KB Output is correct
17 Correct 138 ms 19296 KB Output is correct
18 Correct 147 ms 19564 KB Output is correct
19 Correct 171 ms 23520 KB Output is correct
20 Correct 140 ms 19380 KB Output is correct