Submission #1112739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112739	2024-11-14T17:52:58 Z	wrtt	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	717 ms	61364 KB

jobs

#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb emplace_back
#define mx(a, b) ((a) > (b) ? (a) : (b))
#define mn(a, b) ((a) < (b) ? (a) : (b))
#define graph(n) vector<int> g[(n)+1];
constexpr int mod = 1000000007;

void frx(std::string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}

/*
template <typename T, size_t N>
ostream &operator<<(ostream &os, const T (&arr)[N]) {
  os << "[";
  for(size_t i = 0; i < N; ++i) {
    if(i>0) {
      os << ", ";
    }
    os<<arr[i];
  }
  return os << "]";
}
*/

bool firsttrue(int mid, int a[], int m, int d) {
  if(mid >= m) return 1;
  int b[m];
  for(int i = 0; i < m; ++i) {
    b[i] = (i / mid)+1;
  }
  for(int i = 0; i < m; ++i) {
    if((b[i] - a[i]) > d) return 0;
    if(b[i] > m) return 0;
  }
  return 1;
}
void solve() {
  int n,d,m;
  cin>>n>>d>>m;
  int a[m];
  unordered_map<int,unordered_set<int>> mp;
  for(int i = 0; i < m; ++i) {
    cin>>a[i];
    mp[a[i]].insert(i);
  }
  sort(a,a+m);
  int l = 1; int r = 1e6;
  int ans = 1e6;
  while(l<=r) {
    int mid = (l+r)/2;
    if(firsttrue(mid,a,m,d)) {
      r=mid-1;
      ans=mid;
    }
    else {
      l=mid+1;
    }
  }
  cout<<ans<<"\n";
  int cnt = 0;
  bool visited[100001];
  int line = 0;
  memset(visited,0,sizeof(visited));
  for(int i = 0; i < m; ++i) {
    if(!visited[a[i]]) {
    for(int val : mp[a[i]]) {
      cout<<val+1<<" ";
      ++cnt;
      if(cnt==ans) {
        cout<<"0\n";
        ++line;
        cnt=0;
      }
    }
    visited[a[i]] = 1;
    }
  }
  if(cnt!=0) {
    cout<<"0\n";
    ++line;
  }
  for(int i = line; i < n; ++i) {
    cout<<"0\n";
  }
}
  
signed main() {
    std::ios_base::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    //frx("piggyback");
    #ifdef LOCAL  
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    #ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << elapsed.count() << " seconds\n";
    #endif
    return 0;  
}

Compilation message

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

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	7364 KB	Output isn't correct
2	Incorrect	25 ms	7356 KB	Output isn't correct
3	Incorrect	24 ms	7356 KB	Output isn't correct
4	Incorrect	24 ms	7364 KB	Output isn't correct
5	Incorrect	24 ms	7364 KB	Output isn't correct
6	Incorrect	26 ms	7408 KB	Output isn't correct
7	Incorrect	24 ms	7364 KB	Output isn't correct
8	Incorrect	24 ms	7356 KB	Output isn't correct
9	Correct	38 ms	7060 KB	Output is correct
10	Correct	40 ms	7240 KB	Output is correct
11	Correct	41 ms	7260 KB	Output is correct
12	Correct	98 ms	13896 KB	Output is correct
13	Correct	165 ms	22088 KB	Output is correct
14	Correct	362 ms	29252 KB	Output is correct
15	Runtime error	303 ms	33864 KB	Memory limit exceeded
16	Runtime error	511 ms	44320 KB	Memory limit exceeded
17	Runtime error	645 ms	52040 KB	Memory limit exceeded
18	Runtime error	586 ms	55552 KB	Memory limit exceeded
19	Runtime error	717 ms	61364 KB	Memory limit exceeded
20	Runtime error	630 ms	52184 KB	Memory limit exceeded