Submission #1279022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279022		coquelic	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	226 ms	20872 KiB

jobs

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include <array> 
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define double long double
#define int long long
#define lc u<<1
#define rc u<<1|1
//#define endl "\n"
#define X first
#define Y second
//typedef unsigned long long ll;
typedef long long ll;
typedef pair<ll, ll> PII;
const long long N = 1e6 + 50, M = 2e5 + 5, INF = 0x3f3f3f3f;
const long long maxm = 1e18 + 5, maxn = 3e5 + 5;
//const ll maxm = LLONG_MAX;
const long long mod = 998244353;
//const ll mod = 1e9 + 7;


ll dx[] = { -1,0,1,0 };
ll dy[] = { 0,1,0,-1 };

//__builtin_popcountll();
//a.erase(unique(a.begin(),a.end()),a.end());//去重
//string demo = str.substr(ps,(r-l+1));//截取下标从ps开始的长度为len子串
//找第一次出现的字符的下标也用.find吧
//字符串陋习，尽可能这样获取子串，直接+=会t

ll exgcd(ll a, ll b, ll& x, ll& y);

inline ll gcd(ll a, ll b) {
    return b > 0 ? gcd(b, a % b) : a;
}

ll ksm(ll a, ll b, ll p) {
    ll base = a;
    ll ans = 1;
    while (b) {
        if (b & 1)ans *= base;
        ans %= p;
        base *= base; base %= p;
        b >>= 1;
    }
    return ans % p;
}

void KKLK(ll a, ll b, ll c, ll d) {
    cout << "[ " << a << "," << b << "," << c << "," << d << " ]" << endl;
}

/*
struct cmp {
    bool operator()(node a, node b) {
        return a.d > b.d;//表示小根堆
    }
};*/

ll n, d, m;
pair<ll, ll>a[N];

bool check(ll k) {
    ll now = 1;
    for (int i = 1; i <= m; i++) {
        if (now > n)return false;
        ll nxt = i + k;
        nxt = min(nxt, m + 1);
        if (a[i].X + d >= now) {
            
        }
        else return false;
        ++now; i = nxt - 1;
    }
    return true;
}

void solve() {
    //显然二分
    cin >> n >> d >> m; for (int i = 1; i <= m; i++)cin >> a[i].X, a[i].Y = i;
    sort(a + 1, a + 1 + m);

    ll l = 0, r = m;

    while (l + 1 < r) {
        ll mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        }
        else l = mid;
    }
    
    cout << r << endl;

    ll now = 1;
    for (int i = 1; i <= m; i++) {
        ll nxt = i + r;
        nxt = min(nxt, m + 1);
        for (int j = i; j < nxt; j++)cout << a[j].Y << ' ';
        cout << 0 << endl;
        ++now; i = nxt - 1;
    }
    while (now <= n) {
        cout << 0 << endl; ++now;
    }


}



signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll _t = 1; //cin >> _t;
    while (_t--)solve();
    return 0;
}

/*PonyHex*/
/*SilverWolf__*/


ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll temp = x;
    x = y;
    y = temp - (a / b) * y;
    return g;
}

• Subtask 1: 55 / 100