oj.uz

Submission #629600

# Submission time Handle Problem Language Result Execution time Memory
629600 2022-08-14T17:37:57 Z level Job Scheduling (CEOI12_jobs) C++14
100 / 100
 148 ms 24224 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 2636 KB Output is correct
2 Correct 14 ms 2644 KB Output is correct
3 Correct 19 ms 2628 KB Output is correct
4 Correct 15 ms 2604 KB Output is correct
5 Correct 18 ms 2636 KB Output is correct
6 Correct 15 ms 2636 KB Output is correct
7 Correct 15 ms 2628 KB Output is correct
8 Correct 15 ms 2708 KB Output is correct
9 Correct 25 ms 5276 KB Output is correct
10 Correct 28 ms 5276 KB Output is correct
11 Correct 17 ms 2728 KB Output is correct
12 Correct 32 ms 4936 KB Output is correct
13 Correct 46 ms 7884 KB Output is correct
14 Correct 93 ms 9144 KB Output is correct
15 Correct 95 ms 12256 KB Output is correct
16 Correct 104 ms 16260 KB Output is correct
17 Correct 122 ms 16184 KB Output is correct
18 Correct 131 ms 19660 KB Output is correct
19 Correct 143 ms 24224 KB Output is correct
20 Correct 148 ms 16112 KB Output is correct