Submission #48621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48621	2018-05-17T12:33:29 Z	doowey	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	293 ms	15760 KB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
	
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TEST freopen("in.txt","r",stdin);
#define ab(a) ((a < 0) ? (-(a)) : (a))
#define len(x) ((int)(x).size())
#define ones(x) __builtin_popcount((x))
#define all(x) x.begin(), x.end()

const int N = (int)1e5 + 999;
int n,d;
vector<int>J[N];
int rem[N];

bool can(int k){
  for(int i = 1;i <= n;i ++)
    rem[i] = J[i].size();
  int p = 1;
  int tt = 0;
  int kk;
  for(int i = 1;i <= n;i ++){
    kk = k;
    if(i - p > d)
      return false;
    while(kk > 0 && p <= i){
      if(rem[p] == 0){
        p++;
        continue;
      }
      kk--;
      rem[p]--;
    }
  }
  return true;
}

void output_solution(int x){
  cout << x << "\n";
  int p = 1;
  int tt;
  for(int i = 1;i <= n;i ++ ){
    tt = x;
    while(p <= i and tt > 0){
      if(J[p].empty()){
        p++;
        continue;
      }
      cout << J[p].back() << " ";
      tt--;
      J[p].pop_back();
    }
    cout << "0\n";
  }
}

int main(){
  fastIO;
  int m;
  cin >> n >> d >> m;
  int x;
  for(int i = 1 ;i <= m;i ++){
    cin >> x;
    J[x].push_back(i);
  }
  int lf = 0,rf = m + 1;
  int md;
  while(rf-lf > 1){
    md = (lf + rf) / 2;
    if(can(md))
      rf = md;
    else
      lf = md;
  }
  output_solution(rf);
  return 0;
}

Compilation message

jobs.cpp: In function 'bool can(int)':
jobs.cpp:28:7: warning: unused variable 'tt' [-Wunused-variable]
   int tt = 0;
       ^~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	4212 KB	Output isn't correct
2	Incorrect	29 ms	4636 KB	Output isn't correct
3	Incorrect	25 ms	4940 KB	Output isn't correct
4	Incorrect	34 ms	5212 KB	Output isn't correct
5	Incorrect	33 ms	5500 KB	Output isn't correct
6	Incorrect	25 ms	5840 KB	Output isn't correct
7	Incorrect	26 ms	5840 KB	Output isn't correct
8	Incorrect	26 ms	5840 KB	Output isn't correct
9	Correct	32 ms	6400 KB	Output is correct
10	Correct	33 ms	6400 KB	Output is correct
11	Correct	30 ms	6400 KB	Output is correct
12	Correct	69 ms	6928 KB	Output is correct
13	Correct	89 ms	8880 KB	Output is correct
14	Correct	124 ms	9980 KB	Output is correct
15	Correct	129 ms	11024 KB	Output is correct
16	Correct	293 ms	12688 KB	Output is correct
17	Correct	214 ms	14556 KB	Output is correct
18	Correct	202 ms	14556 KB	Output is correct
19	Correct	259 ms	15760 KB	Output is correct
20	Correct	216 ms	15760 KB	Output is correct