Submission #48578

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48578	2018-05-16T20:40:07 Z	doowey	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	178 ms	15408 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>R[N];
int has_done[N];

bool can(int k){
  for(int i = 0;i < N; i ++ )
    has_done[i] = 0;
  int tt = 0;
  for(int i = 1;i <= d;i ++ )
    tt += len(R[i]);
  if(tt >= (d + 1) * k)
    return false;
  int p = 1;
  for(int i = d + 1;i <= n;i ++ ){
    tt -= len(R[p]);
    p++;
    if(tt >= (d + 1) * k)
      return false;
  }
  return true;
}

void output_solution(int answer){
  cout << answer << "\n";
  for(int j = 0;j < N;j ++ )
    has_done[j] = 0;
  int p = 1;
  int tt;
  for(int i = 1;i <= n;i ++ ){
    tt = answer;
    while(p <= i and tt > 0){
      if(len(R[p]) == has_done[p]){
        p++;
        continue;
      }
      cout << R[p][has_done[p]] << " ";   
      has_done[p]++;
      tt--;
    }
    cout << "0\n";
  }
}

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	3956 KB	Output isn't correct
2	Incorrect	15 ms	4364 KB	Output isn't correct
3	Incorrect	14 ms	4624 KB	Output isn't correct
4	Incorrect	14 ms	5176 KB	Output isn't correct
5	Incorrect	15 ms	5176 KB	Output isn't correct
6	Incorrect	14 ms	5324 KB	Output isn't correct
7	Incorrect	14 ms	5324 KB	Output isn't correct
8	Incorrect	14 ms	5324 KB	Output isn't correct
9	Incorrect	27 ms	6040 KB	Output isn't correct
10	Incorrect	25 ms	6040 KB	Output isn't correct
11	Incorrect	26 ms	6040 KB	Output isn't correct
12	Incorrect	43 ms	7088 KB	Output isn't correct
13	Incorrect	63 ms	8624 KB	Output isn't correct
14	Incorrect	105 ms	9964 KB	Output isn't correct
15	Incorrect	78 ms	9964 KB	Output isn't correct
16	Incorrect	165 ms	11952 KB	Output isn't correct
17	Incorrect	175 ms	14512 KB	Output isn't correct
18	Incorrect	159 ms	14512 KB	Output isn't correct
19	Incorrect	178 ms	15408 KB	Output isn't correct
20	Incorrect	173 ms	15408 KB	Output isn't correct