Submission #300189

#	Time	Username	Problem	Language	Result	Execution time	Memory
300189		model_code	Finding Routers (IOI20_routers)	Java	100 / 100	136 ms	12300 KiB

routers

public class routers {
	int[] ans, dist;
	int ctr = 0;
	
	void bs(int s, int e, int a, int b) {
		if (a > b) return;
		if (e - s == b - a) {
			for (int i = s; i <= e; i++) {
				dist[ctr++] = i;
			}
			return;
		}
		if (s + 1 == e) {
			if (grader.use_detector(e) == a) {
				dist[ctr++] = e;
			} else {
				dist[ctr++] = s;
			}
			return;
		}
		int m = (s + e) / 2;
		int hi = grader.use_detector(m);
		bs(s, m - 1, a, hi - 1);
		bs(m, e, hi, b);
	}
	
	int[] find_routers(int l, int n, int q) {
		ctr = 0;
		dist = new int[n];
		bs(0, l, 0, n - 2);
		ans = new int[n];
		ans[0] = 0;
		for (int i = 1; i < n; i++) {
			ans[i] = 2 * dist[i - 1] - ans[i - 1];
		}
		return ans;
	}
}

• Subtask 1: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 40 / 40