Submission #927908

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927908	2024-02-15T13:58:27 Z	megaminion	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1000 ms	44648 KB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define For(i, a, b) for(int i = (a); i < (b); ++i)
#define pb push_back
#define ins insert
#define rsz resize
#define f first
#define s second
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
void setIO(string name = "")
{
    cin.tie(0)->sync_with_stdio(0);
    if (sz(name))
    {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
void prt(bool f) 
{
    // Unfortunatley, atcoder checker rejects YES/NO
    cout<<((f)? "Yes\n" : "No\n");
}
using indexed_set = tree<int,null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vb = vector<bool>;
using vs = vector<str>;
using mi = map<int, int>;
using ml = map<ll, ll>;
using si = set<int>;
using sl = set<ll>;
using sc = set<char>;
const ld PI = 2*acos(0.0);
const ld EPS = 1e-11;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const int inv2 = (MOD+1)/2;
const ll INF = 1e12;
const int M = 1e6;
const int N = 1e5;
#define int ll

int n, d, m;
int a[M], mp[N+1];
vector<int> v[N+1];
vector<int> p[N+1];

bool ok(int x, bool flag)
{
    bool ret = true;
    multiset<int> s;
    for(int i = 1; i <= n; ++i)
    {
        v[i].clear();
        for(int j = 0; j < mp[i]; ++j)
        {
            s.ins(i);
        }
        for(int j = 0; j < x; ++j)
        {
            if(s.empty()) break;
            ret &= i - *s.begin() <= d;
            if(flag)
            {
                v[i].pb(p[*s.begin()].back());
                p[*s.begin()].pop_back();
            }
            s.erase(s.begin());
        }
    }
    return ret;
}

void solve()
{
    cin>>n>>d>>m;
    for(int i = 0; i < m; ++i)
    {
        cin>>a[i];
        mp[a[i]]++;
        p[a[i]].pb(i+1);
    }
    int L = 1, R = 1e7, mid;
    while(L < R)
    {
        mid = L + (R - L) / 2;
        if(ok(mid, false))
        {
            R = mid;
        }
        else
        {
            L = mid+1;
        }
    }
    cout<<L<<endl;
    assert(ok(L, true));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < sz(v[i]); ++j)
        {
            cout<<v[i][j];
            if(j + 1 != sz(v[i])) cout<<" ";
            else cout<<" 0";
        }
        if(v[i].empty())
        {
            cout<<"0";
        }
        if(i != n) cout<<endl;
    }
}

int32_t main()
{
    setIO();
    int t = 1;
    // cin>>t;
    for(int i = 1; i <= t; ++i)
    {
        solve();
    }
    return 0;
}

/*

*/

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	374 ms	13080 KB	Output is correct
2	Correct	340 ms	13076 KB	Output is correct
3	Correct	353 ms	13072 KB	Output is correct
4	Correct	341 ms	13076 KB	Output is correct
5	Correct	378 ms	13076 KB	Output is correct
6	Correct	356 ms	13092 KB	Output is correct
7	Correct	354 ms	13072 KB	Output is correct
8	Correct	366 ms	13076 KB	Output is correct
9	Correct	222 ms	10580 KB	Output is correct
10	Correct	228 ms	10980 KB	Output is correct
11	Correct	146 ms	9848 KB	Output is correct
12	Correct	331 ms	15516 KB	Output is correct
13	Correct	505 ms	22820 KB	Output is correct
14	Correct	600 ms	26572 KB	Output is correct
15	Correct	826 ms	30436 KB	Output is correct
16	Runtime error	805 ms	34500 KB	Memory limit exceeded
17	Execution timed out	1024 ms	44648 KB	Time limit exceeded
18	Execution timed out	1044 ms	32784 KB	Time limit exceeded
19	Execution timed out	1067 ms	37840 KB	Time limit exceeded
20	Execution timed out	1012 ms	44608 KB	Time limit exceeded