oj.uz

Submission #631543

# Submission time Handle Problem Language Result Execution time Memory
631543 2022-08-18T08:20:48 Z andrei_boaca Job Scheduling (CEOI12_jobs) C++14
100 / 100
 161 ms 20800 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define inf 1e9+5
#define nl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a) memset((a),0,sizeof(a))
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<int> vi;
typedef pair<int,int> pi;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
 
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
 
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
 
bool valid(int x, int n, vi a, int d){
 
  for(int i=1; i<=n; i++){
    a[i]=max(0, a[i]-x);
    // cout<<a[i]<<" ";
    if(a[i]/d > x) return false;
    a[i+1]+=a[i];
  }
  return a[n]==0;
 
}
 
void solve(){
  int n, d, m;
  cin>>n>>d>>m;
 
  vi v(m);
  vi a(n+1, 0);
  vector<int> q[n+1];
 
 
  for(int i=0; i<m; i++){
    cin>>v[i];
    a[v[i]]++;
    q[v[i]].pb(i+1);
  }
  // for(int i=1; i<=n; i++){
  //   cout<<a[i]<<" ";
  // }
  // cout<<nl;
  // cout<<valid(1, n, a, d);
  int lo=1, hi=1e6+10;
  while(hi-lo>1){
    int mid = (lo+hi)/2;
    if(valid(mid,n,a,d)) hi=mid;
    else lo=mid+1; 
  }
 
  int ans=0;
  if(valid(lo,n,a,d)){ cout<<lo; ans=lo;}
  else {cout<<hi; ans=hi;}
 
  cout<<nl;
 
  queue<int> qq;
 
  for(int i=1; i<n+1; i++){
    for(int j=0; j<q[i].size(); j++){
      qq.push(q[i][j]);
    }
  }
 
  int ct=0, count=0;
  while(!qq.empty()){
      count++;
    while(ct!=ans && !qq.empty()){
      ct++;
      cout<<qq.front()<<" ";
      qq.pop();
    }
    cout<<"0\n";
    ct=0;
  }
  count=n-count;
  while(count--) cout<<"0\n";
}
 
int main() {
  #ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
  #endif
 
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
 
  int t=1;
  // cin>>t;
  while(t--){
    solve();
    // cout<<nl;
  }
 
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int j=0; j<q[i].size(); j++){
      |                  ~^~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("Error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2380 KB Output is correct
2 Correct 14 ms 2336 KB Output is correct
3 Correct 14 ms 2376 KB Output is correct
4 Correct 14 ms 2380 KB Output is correct
5 Correct 14 ms 2380 KB Output is correct
6 Correct 14 ms 2420 KB Output is correct
7 Correct 16 ms 2312 KB Output is correct
8 Correct 16 ms 2300 KB Output is correct
9 Correct 25 ms 5252 KB Output is correct
10 Correct 24 ms 5248 KB Output is correct
11 Correct 15 ms 2224 KB Output is correct
12 Correct 29 ms 4180 KB Output is correct
13 Correct 46 ms 6800 KB Output is correct
14 Correct 71 ms 9088 KB Output is correct
15 Correct 75 ms 10448 KB Output is correct
16 Correct 122 ms 13516 KB Output is correct
17 Correct 135 ms 16076 KB Output is correct
18 Correct 128 ms 16668 KB Output is correct
19 Correct 140 ms 20800 KB Output is correct
20 Correct 161 ms 16184 KB Output is correct