Submission #466270

#	Time	Username	Problem	Language	Result	Execution time	Memory
466270		3footninja	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	213 ms	14812 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using ll = long long;
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define sz(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define dbg(...) [](const auto& ...x) { char c = '='; cerr << #__VA_ARGS__ << " "; ((cerr << exchange(c, ',') << " " << x), ...); cerr << endl; } (__VA_ARGS__);
#define dbgc(v) {cerr << #v << " : "; for (auto x : v) cerr << x << ' '; cerr << endl;}
#define dbgp(x) cerr << #x << "= {" << (x.first) << ", " << (x.second) << "}" << endl;
template<typename T> inline T abs(T a) { return ((a < 0) ? -a : a); } 
template<typename T> inline T sqr(T a) { return a * a; }

int n, d, m;
vector<vi> v;

void read_input() {
   cin >> n >> d >> m;
   v.resize(n + 1);
   rep (i, 1, m + 1) {
      int t;   cin >> t;
      v[t].pb(i);
   }
   // v[day] = [requests recieved on that day]; 
}

bool good (int x) {
   // x is the number of machines used, the more the x the lesser days it will take. So good.
   int ct = 0;
   vi a;
   rep (i, 0, n) {
      rep (j, 0, sz(v[i])) {
         a.pb(v[i][j]);
      }
   }
   /* int j = 0, placed = 0;
   while (placed < m) {
      int temp = 0;
      while (j < sz(a)) {
         if (temp + 1 <= x) {
            temp++;
            j++;
         } else {
            ct++;
            break;
         }
      }
      placed += temp;
   }  */ 
   ct += ((sz(a) + x - 1) / x);
   return (ct <= n);
}

void solve () {
   int l = 0;  // always bad, need to deal with this case in the good function tho
   int r = 1e6 + 5; // a machine for every request, good
   while (r - l > 1) {
      int m = l + (r - l) / 2;
      if (good(m)) {
         r = m;
      } else {
         l = m;
      }
   }
   cout << r << "\n";
  	rep (i, 0, n) {
      cout << 0 << "\n";
    }
}    

void setIO(string name = "")
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   if (sz(name)) {
      freopen((name + ".in").c_str(), "r", stdin);
      freopen((name + ".out").c_str(), "w", stdout);
   }
}

signed main()
{
   setIO();
   read_input();
   int t = 1;
   // cin >> t;
   while (t--) {
      solve();
   }   
   return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 100