oj.uz

답안 #306539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306539 2020-09-25T19:51:42 Z Swab Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 95 ms 10564 KB 
import java.util.Arrays;
import java.util.Scanner;

class Week2Jobs {

	public static int n, d, m;
	public static int[] days;
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		d = scanner.nextInt();
		m = scanner.nextInt();
		
		days = new int[m];
		
		Day[] days2 = new Day[m];
		
		for(int i=0; i<m; i++) {
			int a = scanner.nextInt();
			days[i] = a;
			days2[i] = new Day(i,a);
		}
		
		Arrays.sort(days);
		
		int lowerbound = 1;
		int upperbound = m;
		
		int a = lowerbound;
		int b = upperbound;
		
		while(a!=b) {
			
			int mid = (a+b)/2;
			
			if(works(mid)) {
				b=mid;
			}
			else {
				a = mid+1;
			}
			
		}
		
		System.out.println(a);
		
		int[] marked = new int[a];
		
		Arrays.sort(days2);
		
		
		
		for(int i=0; i<m; i++) {
			if(marked[i%a]==0) {
				marked[i%a] = days2[i].day;
				//System.out.println(days2[i].day+" " + days2[i].index+" ");
				continue;
			}
			if(marked[i%a]>=days2[i].day) {
				int temp = marked[i%a]+1;
				marked[i%a] = temp;
				days2[i] = new Day(days2[i].index, temp);
			}
			//System.out.println(days2[i].day+" "+days2[i].index+ " ");
			//System.out.println(marked[i%a]);
			marked[i%a] = days2[i].day;
		}
		
		int j = 0;
		for(int i=1; i<=n; i++) {
			while(j<m&&days2[j].day==i) {
				System.out.print(days2[j].index+1 + " ");
				j++;
			}
			System.out.println("0");
		}
		
		
		
	}
	
	public static boolean works(int mid) {
		
		int[] marked = new int[mid];
		
		for(int i=0; i<m; i++) {
			if(marked[i%mid]==0) {
				marked[i%mid] = days[i];
				continue;
			}
			if(marked[i%mid]>=days[i]) {
				int temp = marked[i%mid]+1;
				if(temp-days[i]>d) {
					return false;
				}
				marked[i%mid] = temp;
				continue;
			}
			marked[i%mid] = days[i];
		}
		
		return true;
		
	}
	
	public static class Day implements Comparable<Day>{
		
		int index, day;
		
		public Day(int index, int day) {
			this.index = index;
			this.day = day;
		}

		
		public int compareTo(Day o) {
			
			return day-o.day;
		}
		
		
		
	}

}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 85 ms 10480 KB Execution failed because the return code was nonzero
2 Runtime error 83 ms 10228 KB Execution failed because the return code was nonzero
3 Runtime error 90 ms 10268 KB Execution failed because the return code was nonzero
4 Runtime error 82 ms 10432 KB Execution failed because the return code was nonzero
5 Runtime error 84 ms 10300 KB Execution failed because the return code was nonzero
6 Runtime error 85 ms 10324 KB Execution failed because the return code was nonzero
7 Runtime error 84 ms 10104 KB Execution failed because the return code was nonzero
8 Runtime error 84 ms 10360 KB Execution failed because the return code was nonzero
9 Runtime error 83 ms 10360 KB Execution failed because the return code was nonzero
10 Runtime error 86 ms 10564 KB Execution failed because the return code was nonzero
11 Runtime error 87 ms 10364 KB Execution failed because the return code was nonzero
12 Runtime error 88 ms 10140 KB Execution failed because the return code was nonzero
13 Runtime error 86 ms 10368 KB Execution failed because the return code was nonzero
14 Runtime error 85 ms 10360 KB Execution failed because the return code was nonzero
15 Runtime error 84 ms 10500 KB Execution failed because the return code was nonzero
16 Runtime error 84 ms 10228 KB Execution failed because the return code was nonzero
17 Runtime error 82 ms 10360 KB Execution failed because the return code was nonzero
18 Runtime error 83 ms 10356 KB Execution failed because the return code was nonzero
19 Runtime error 95 ms 10488 KB Execution failed because the return code was nonzero
20 Runtime error 91 ms 10480 KB Execution failed because the return code was nonzero