Submission #883260

#TimeUsernameProblemLanguageResultExecution timeMemory
883260ant102Job Scheduling (CEOI12_jobs)C++14
55 / 100
560 ms65536 KiB
// 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); }
#Verdict Execution timeMemoryGrader output
Fetching results...