Submission #1090986

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090986	2024-09-19T11:30:55 Z	wrtt	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	261 ms	65536 KB

jobs

// Dost SEFEROĞLU

#include "bits/stdc++.h"
//#include "windows.h"

#define int long long
#define mx(a, b) ((a) > (b) ? (a) : (b))
#define mn(a, b) ((a) < (b) ? (a) : (b))
constexpr int mod = 1000000007;

int d;
int n;

bool firsttrue(int mid, int a[], int m) {
  if(mid >= m) {
    return 1;
  }
  int currday = 1;
  int i = 0;
  int maxdelay = 0;
  while(i < m && currday <= n) {
    maxdelay=mx(maxdelay, currday-a[i]);
    ++currday;
    i+=mid;
    if(maxdelay > d) return 0;
  }
  return 1;
}

bool customsort(std::pair<int,int> a, std::pair<int,int> b) {
  return a.second < b.second;
}

void solve() {
  int m;
  std::cin>>n>>d>>m;
  int a[m];
  std::unordered_map<int,int> mp;
  for(int i = 0; i < m; ++i) {
    std::cin>>a[i];
    mp[i] = a[i];
  }
  std::vector<std::pair<int,int>> v(mp.begin(), mp.end());
  std::sort(v.begin(), v.end(), customsort);
  std::sort(a,a+m);
  int l = 1; int r = 1000000;
  int ans = -1;
  while(l<=r) {
    int mid = (l+r)/2;
    if(firsttrue(mid,a,m)) {
      ans=mid;
      r=mid-1;
    }
    else {
      l=mid+1;
    }
  }
  std::cout<<ans<<"\n";
  int curr = 0;
  for(auto i : v) {
    if(curr==0) {
      std::cout<<i.first+1<<" ";
      ++curr;
    }
    else if(curr%ans == 0) {
      std::cout<<i.first+1<<" 0\n";
    }
    else {
      std::cout<<i.first+1<<" ";
    }
    ++curr;
  }
  for(int i = curr/2; i < n; ++i) {
    std::cout<<0<<"\n";
  }
  //std::cout<<curr<<"\n";
}

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    int t = 1;
    //std::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;
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	7876 KB	Output isn't correct
2	Incorrect	24 ms	7888 KB	Output isn't correct
3	Incorrect	20 ms	7888 KB	Output isn't correct
4	Incorrect	20 ms	7632 KB	Output isn't correct
5	Incorrect	19 ms	7616 KB	Output isn't correct
6	Incorrect	21 ms	7632 KB	Output isn't correct
7	Incorrect	21 ms	7864 KB	Output isn't correct
8	Incorrect	20 ms	7888 KB	Output isn't correct
9	Incorrect	25 ms	7888 KB	Unexpected end of file - int32 expected
10	Incorrect	26 ms	7776 KB	Unexpected end of file - int32 expected
11	Incorrect	27 ms	7620 KB	Unexpected end of file - int32 expected
12	Correct	61 ms	15224 KB	Output is correct
13	Incorrect	82 ms	21628 KB	Unexpected end of file - int32 expected
14	Correct	133 ms	30652 KB	Output is correct
15	Runtime error	135 ms	36640 KB	Memory limit exceeded
16	Runtime error	184 ms	42936 KB	Memory limit exceeded
17	Runtime error	215 ms	49084 KB	Memory limit exceeded
18	Runtime error	232 ms	60912 KB	Memory limit exceeded
19	Runtime error	261 ms	65536 KB	Execution killed with signal 9
20	Runtime error	205 ms	48992 KB	Memory limit exceeded