Submission #629600

#	Time	Username	Problem	Language	Result	Execution time	Memory
629600		level	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	148 ms	24224 KiB

jobs

#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 (stderr)

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 / 100