Submission #883260

#	Time	Username	Problem	Language	Result	Execution time	Memory
883260		ant102	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	560 ms	65536 KiB

jobs

//                      c++
#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <cstring>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <bitset>
#include <cstdio>
#include <ctime>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
#define ll  long long// double
const ll r4ch[]{0, 1, 0, -1};
const ll c4ch[]{1, 0, -1, 0};
const ll drect[]{0, 1, 2, 3};
#define fall(v)  for (auto &it: v)
#define fallj(v, it) for (auto &it: v)
#define cfall(v) for (auto &it: v) cin >> it
#define cpfall(v) for (auto &it: v) cin >> it.first >> it.second
#define fn(n) for (ll i = 0; i < n; i++)
#define nfj(n, i) for (ll i = n-1; i > 0; i-)
#define fnn for (ll i = 0; i < n; i++)
#define fnj(n, i) for (ll i = 0; i < n; i++)
#define sortcp(v, cp) sort(v.begin(), v.end(), cp)
#define sort(v) sort(v.begin(), v.end())
#define gsort(v) fall(v){it = -it;}sort(v);fall(v){it = -it;}
#define vec vector
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define lpll pair<ll, pll>
#define plll pair<pll, ll>
#define vll vec<ll>
#define vbl vec<bool>
#define mvbl(nameofboolvec, sizeofboolvec) vec<bool> nameofboolvec(sizeofboolvec, false);
#define vvll vec<vll>
#define vvbl vec<vbl>
#define vpll vec<pair<ll, ll>>
#define mll map<ll, ll>
#define sll set<ll>
#define msll multiset<ll>
#define ve(nameofvecter, lengthofvec) vll nameofvecter(lengthofvec)
#define vep(nameofvecter, lengthofvec) vpll nameofvecter(lengthofvec)
#define cve(nameofvecter, lengthofvec) ve(nameofvecter, lengthofvec); cfall(nameofvecter);
#define cvep(nameofvecter, lengthofvec) vep(nameofvecter, lengthofvec); cpfall(nameofvecter);
#define cvesr(nameofvecter, lengthofvec) cve(nameofvecter, lengthofvec); sort(nameofvecter)
#define c(n) ll n; cin >> n;
#define ca(n) cin >> n;
#define co1(n) cout << n << endl;
#define co2(n, m) cout << n << ' ' << m << endl;
#define co3(a, b, c) cout << a << ' ' << b << ' ' << c << endl;
#define cn ll n; cin >> n;
#define cim ll m; cin >> m;
#define cq ll q; cin >> q;
#define grapher(nameofvecter, numberofnods, numberofedges) vvll nameofvecter(numberofnods); fn(numberofedges){ c(a);c(b);a--;b--;nameofvecter[a].push_back(b); nameofvecter[b].push_back(a); } vec<bool> del (numberofnods, false);
#define graphered(nameofvecter, numberofnods, numberofedges) vvll nameofvecter(numberofnods); fn(numberofedges){ c(a);c(b);a--;b--;nameofvecter[a].push_back(b); nameofvecter[b].push_back(a); }
#define ftst c(testcases); for (ll testcase = 0; testcase < testcases; testcase++)
#define onevve(nameofvecter) cn;cve(nameofvecter, n);
#define twovve(the_second_input, nameofvecter) cn;c(the_second_input);cve(nameofvecter, n);
#define se second
#define fi first
#define ins(theset, thevaluetoinsert) theset.insert(thevaluetoinsert);
#define era(theset, thevaluetoerase) theset.erase(theset.find(thevaluetoerase));
#define im int main()
#define re return
#define wht while(true)

map<ll, vll> runa(ll n, vll v, map<ll, msll> in, ll d, ll co)
{
    map<ll, vll> ans;
    ll day = 1;
    ll left = co;
    fall(v)
    {
        if(day < it)
        {
            day = it; left = co-1;
            ans[day].push_back(*in[it].begin());
            in[it].erase(*in[it].begin());
        }else
        {
            if(left == 0)
            {
                day++;
                left = co-1;
                ans[day].push_back(*in[it].begin());
                in[it].erase(*in[it].begin());
                
            }else
            {
                left--;
                ans[day].push_back(*in[it].begin());
                in[it].erase(*in[it].begin());
            }
        }
    }
    re ans;
}
void coutans(map<ll, vll>  ans,ll n)
{
    ll i = 1;
    while (i <= n) {
        if(ans.find(i) != ans.end())
            fallj(ans[i], it2)
            {
                cout << it2+1 << ' ';
            }
        cout << " 0" << endl;
        i++;
    }
}
bool run(ll n, vll v, map<ll, msll> in, ll d, ll co)
{
    ll day = 1;
    ll left = co;
    fall(v)
    {
        if(day < it)
        {
            day = it; left = co-1;
        }else
        {
            if(left == 0)
            {
                day++;
                left = co-1;
                if(day > d + it || day > n)
                {
                    re 0;
                }
            }else
            {
                left--;
                if(day > d + it || day > n)
                {
                    re 0;
                }
            }
        }
    }
    re 1;
}
void bisr(ll n, vll v, map<ll, msll> in, ll d)
{
    ll m = v.size();
    ll l = -1;
    ll r = m;
    while (true) {
        if(l + 1 == r)
        {
            co1(r);
            coutans(runa(n, v, in, d, r), n);
            re;
        }
        ll mid = (l + r) / 2;
        if(run(n, v, in, d, mid))
        {
            r = mid;
        }else
        {
            l = mid;
        }
        
    }
}
im
{
    cn;c(d);cim;
    cve(v, m);
    map<ll, msll> in;
    fn(m)
        in[v[i]].insert(i);
    sort(v);
    bisr(n, v, in, d);
    
}

• Subtask 1: 55 / 100