Submission #847121

#TimeUsernameProblemLanguageResultExecution timeMemory
847121airthsJob Scheduling (CEOI12_jobs)C++17
90 / 100
1053 ms22788 KiB
/* * * ^v^ * */ #include <iostream> #include <numeric> #include <set> #include <iomanip> #include <chrono> #include <queue> #include <string> #include <vector> #include <functional> #include <map> #include <bitset> #include <algorithm> #include <array> #include <random> using namespace std; using ll = int; using ld = long double; #define iamtefu ios_base::sync_with_stdio(false); cin.tie(0); #define fl(i,a,n) for (ll i(a); i<n; i++) #define rfl(i,a,n) for (ll i(n-1); i>=a; i--) #define ty int _; for(cin>>_; _--;) #define print(a) for(auto ele:a){cout<<ele<<" ";}cout<<'\n'; template <typename L, typename R> inline bool chmax(L &a, R &b){if (a<b){a=b;return 1;}return 0;} template <typename L, typename R> inline bool chmin(L &a, R &b){if (a>b){a=b;return 1;}return 0;} template <typename L, typename R> ostream& operator<<(ostream &fout, const pair<L, R> &p){ fout<<"{"<<p.first<<","<<p.second<<"}"; return fout; } template <typename T> ostream& operator<<(ostream &fout, const vector <T> &v){ for (auto &x:v){ fout<<x<<" "; } fout<<"\n"; return fout; } template <typename T> ostream& operator<<(ostream &fout, const set <T> &st){ for (auto &x:st){ fout<<x<<" "; } fout<<"\n"; return fout; } template <typename K, typename V> ostream& operator<<(ostream &fout, const map<K, V> &mp){ fout<<"["; for (auto &[x,y]:mp){ fout<<x<<":"<<y<<" "; } fout<<"]\n"; return fout; } ll gcd(ll a, ll b){ if (b==0){ return a; } return gcd(b, a%b); } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll pw(ll a, ll b, ll m){ ll res=1; a%=m; while (b){ if (b&1){ res=(res*a)%m; } a=(a*a)%m; b/=2; } return res; } void scn(){ ll n, d, m; cin>>n>>d>>m; vector <ll> a(m); fl(i,0,m){ cin>>a[i]; } vector <vector <pair<ll,ll>>> val(n+1); fl(i,0,m){ val[a[i]].push_back({a[i]+d, i+1}); } auto bin=[&](ll mid){ priority_queue<pair<ll,ll>> pq; fl(i,1,n+1){ for (auto x:val[i]){ // cout<<x; pq.push({-x.first, x.second}); } // cout<<'\n'; if (pq.size() && -pq.top().first<i){ return false; } ll cur = mid; while (cur-- && pq.size()){ pq.pop(); } } return true; }; // cout<<bin(1)<<" "<<bin(2)<<'\n'; ll l = 1, r = m+1; while (l<=r){ ll mid = (l+r)/2; if (bin(mid)){ r = mid-1; } else { l = mid+1; } } cout<<l<<'\n'; priority_queue<pair<ll,ll>> pq; vector <vector <ll>> ans(n+1); fl(i,1,n+1){ for (auto x:val[i]){ pq.push({-x.first, x.second}); } ll cur = l; while (cur-- && pq.size()){ ans[i].push_back(pq.top().second); pq.pop(); } ans[i].push_back(0); } fl(i,1,n+1){ fl(j,0,ans[i].size()){ cout<<ans[i][j]<<" \n"[j==(ans[i].size()-1)]; } } // not necessarily distinct // right down } int main(){ iamtefu; #if defined(airths) auto t1=chrono::high_resolution_clock::now(); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ty { scn(); } #if defined(airths) auto t2=chrono::high_resolution_clock::now(); ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count(); ti*=1e-6; cerr<<"Time: "<<setprecision(12)<<ti; cerr<<"ms\n"; #endif return 0; }

Compilation message (stderr)

jobs.cpp: In function 'void scn()':
jobs.cpp:27:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | #define fl(i,a,n) for (ll i(a); i<n; i++)
......
  146 |   fl(j,0,ans[i].size()){
      |      ~~~~~~~~~~~~~~~~~            
jobs.cpp:146:3: note: in expansion of macro 'fl'
  146 |   fl(j,0,ans[i].size()){
      |   ^~
jobs.cpp:147:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    cout<<ans[i][j]<<" \n"[j==(ans[i].size()-1)];
      |                           ~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...