oj.uz

Submission #78619

# Submission time Handle Problem Language Result Execution time Memory
78619 2018-10-06T17:33:18 Z ekrem Job Scheduling (CEOI12_jobs) C++
60 / 100
 1000 ms 15080 KB 
 #include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define N 1000005
using namespace std;
typedef pair < int , int > ii;
int n, m, d, bas = 1, son;
ii a[N];

bool dene(int x){
	queue < int > q;
	int ind = 1;
	for(int i = 1; i <= n; i++){
		while(a[ind].st == i){
			q.push(i);
			ind++;
		}
		int say = 0;
		for(int j = 1; j <= x; j++)
			if(!q.empty()){
				if(i - q.front() > d)
					return 0;
				else
					q.pop();
			}
	}
	if(!q.empty())
		return 0;
	return 1;
}

void bastir(int x){
	queue < int > q;
	int ind = 1;
	for(int i = 1; i <= n; i++){
		while(a[ind].st == i){
			q.push(ind);
			ind++;
		}
		int say = 0;
		for(int j = 1; j <= x; j++)
			if(!q.empty()){
				cout << a[q.front()].nd << " ";
				q.pop();
			}
		cout << 0 << endl;
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d %d",&n ,&d ,&m);
	son = m;
	for(int i = 1; i <= m; i++){
		scanf("%d",&a[i].st);
		a[i].nd = i;
	}
	sort(a + 1, a + m + 1);
	while(bas < son)
		if(dene(orta))
			son = orta;
		else
			bas = orta + 1;
	cout << orta << endl;
	bastir(orta);
	return 0;
}

Compilation message

jobs.cpp: In function 'bool dene(int)':
jobs.cpp:21:7: warning: unused variable 'say' [-Wunused-variable]
   int say = 0;
       ^~~
jobs.cpp: In function 'void bastir(int)':
jobs.cpp:43:7: warning: unused variable 'say' [-Wunused-variable]
   int say = 0;
       ^~~
jobs.cpp: In function 'int main()':
jobs.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n ,&d ,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i].st);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 2348 KB Output is correct
2 Correct 804 ms 2756 KB Output is correct
3 Correct 755 ms 3248 KB Output is correct
4 Correct 768 ms 3544 KB Output is correct
5 Correct 798 ms 3848 KB Output is correct
6 Correct 793 ms 4188 KB Output is correct
7 Correct 765 ms 4416 KB Output is correct
8 Correct 803 ms 4692 KB Output is correct
9 Execution timed out 1062 ms 4692 KB Time limit exceeded
10 Execution timed out 1060 ms 4692 KB Time limit exceeded
11 Correct 104 ms 5092 KB Output is correct
12 Correct 194 ms 7540 KB Output is correct
13 Correct 267 ms 9964 KB Output is correct
14 Execution timed out 1072 ms 10592 KB Time limit exceeded
15 Correct 458 ms 15080 KB Output is correct
16 Execution timed out 1085 ms 15080 KB Time limit exceeded
17 Execution timed out 1077 ms 15080 KB Time limit exceeded
18 Execution timed out 1080 ms 15080 KB Time limit exceeded
19 Execution timed out 1089 ms 15080 KB Time limit exceeded
20 Execution timed out 1085 ms 15080 KB Time limit exceeded