Submission #300179

#	Time	Username	Problem	Language	Result	Execution time	Memory
300179		model_code	Handcrafted Gift (IOI20_gift)	Java	100 / 100	880 ms	52384 KiB

gift

// limli-full
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class gift {
	int construct(int n, int r, int[] a, int[] b, int[] x) {
		ArrayList<ii> ones = new ArrayList<>(), twos = new ArrayList<>();
		for (int i = 0; i < r; i++) {
			ii range = new ii(a[i], b[i]);
			if (x[i] == 1) {
				ones.add(range);
			} else {
				twos.add(range);
			}
		}
		ones = combine(ones);
		for (ii range : twos) {
			if (range.first == range.second) {
				return 0;
			}
			if (ones.isEmpty()) continue;
			if(!rangeIsValid(ones, range)){
				return 0;
			}
		}
		char[] ans = new char[n];
		Arrays.fill(ans, 'R');
		int pos = 0;
		for (int i = 1; i < n; i++) {
			if (!ones.isEmpty() && ones.get(pos).first <= i - 1 && i <= ones.get(pos).second) {
				ans[i] = ans[i - 1];
			} else {
				ans[i] = (char)('R' + 'B' - ans[i - 1]);
			}
			if (pos + 1 < ones.size() && ones.get(pos).second <= i) {
				pos++;
			}
		}
		String str = new String(ans);
		grader.craft(str);
		return 1;
	}

	boolean rangeIsValid(ArrayList<ii> list, ii range) {
		int a = 0, b = list.size() - 1;
		while (a < b) {
			int m = (a + b + 1) / 2;
			if (list.get(m).first <= range.first) {
				a = m;
			} else {
				b = m - 1;
			}
		}
		ii onesrange = list.get(a);
		if (onesrange.first <= range.first && range.second <= onesrange.second) {
			return false;
		}
		return true;
	}

	int max(int a, int b) {
		if (a > b)
			return a;
		return b;
	}

	ArrayList<ii> combine(ArrayList<ii> ranges) {
		ArrayList<ii> ans = new ArrayList<>();
		if (ranges.isEmpty())
			return ans;
		Collections.sort(ranges);
		int a = ranges.get(0).first, b = ranges.get(0).second;
		for (ii range : ranges) {
			if (range.first <= b) {
				b = max(b, range.second);
			} else {
				ans.add(new ii(a, b));
				a = range.first;
				b = range.second;
			}
		}
		ans.add(new ii(a, b));
		return ans;
	}
}

class ii implements Comparable<ii> {
	public int first;
	public int second;

	public ii(int first, int second) {
		this.first = first;
		this.second = second;
	}

	@Override
	public int compareTo(ii other) {
		if (first != other.first) {
			return first - other.first;
		}
		return second - other.second;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30