Submission #300189

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300189	2020-09-16T22:30:51 Z	model_code	Finding Routers (IOI20_routers)	Java 11	100 / 100	136 ms	12300 KB

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.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	10232 KB	Output is correct
2	Correct	86 ms	10376 KB	Output is correct
3	Correct	84 ms	10208 KB	Output is correct
4	Correct	89 ms	10132 KB	Output is correct
5	Correct	87 ms	10184 KB	Output is correct
6	Correct	84 ms	10356 KB	Output is correct
7	Correct	78 ms	10472 KB	Output is correct
8	Correct	82 ms	10232 KB	Output is correct
9	Correct	78 ms	10228 KB	Output is correct
10	Correct	84 ms	10232 KB	Output is correct
11	Correct	77 ms	10084 KB	Output is correct
12	Correct	82 ms	10336 KB	Output is correct
13	Correct	83 ms	10140 KB	Output is correct
14	Correct	79 ms	10088 KB	Output is correct
15	Correct	79 ms	10360 KB	Output is correct
16	Correct	78 ms	10232 KB	Output is correct
17	Correct	78 ms	10360 KB	Output is correct
18	Correct	82 ms	10104 KB	Output is correct
19	Correct	81 ms	10180 KB	Output is correct
20	Correct	79 ms	10212 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	10444 KB	Output is correct
2	Correct	82 ms	9996 KB	Output is correct
3	Correct	92 ms	10376 KB	Output is correct
4	Correct	86 ms	10320 KB	Output is correct
5	Correct	86 ms	10136 KB	Output is correct
6	Correct	85 ms	10108 KB	Output is correct
7	Correct	84 ms	10396 KB	Output is correct
8	Correct	83 ms	10196 KB	Output is correct
9	Correct	84 ms	10016 KB	Output is correct
10	Correct	86 ms	10276 KB	Output is correct
11	Correct	80 ms	10356 KB	Output is correct
12	Correct	84 ms	10364 KB	Output is correct
13	Correct	81 ms	10364 KB	Output is correct
14	Correct	83 ms	10228 KB	Output is correct
15	Correct	90 ms	10300 KB	Output is correct
16	Correct	82 ms	10164 KB	Output is correct
17	Correct	83 ms	10232 KB	Output is correct
18	Correct	83 ms	10344 KB	Output is correct
19	Correct	84 ms	10212 KB	Output is correct
20	Correct	80 ms	10568 KB	Output is correct

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	10348 KB	Output is correct
2	Correct	83 ms	10196 KB	Output is correct
3	Correct	81 ms	10272 KB	Output is correct
4	Correct	83 ms	10268 KB	Output is correct
5	Correct	81 ms	10472 KB	Output is correct
6	Correct	85 ms	10140 KB	Output is correct
7	Correct	83 ms	10160 KB	Output is correct
8	Correct	84 ms	10252 KB	Output is correct
9	Correct	84 ms	10220 KB	Output is correct
10	Correct	79 ms	10360 KB	Output is correct
11	Correct	80 ms	10112 KB	Output is correct
12	Correct	82 ms	10216 KB	Output is correct
13	Correct	77 ms	10228 KB	Output is correct
14	Correct	78 ms	10360 KB	Output is correct
15	Correct	88 ms	10188 KB	Output is correct
16	Correct	82 ms	10312 KB	Output is correct
17	Correct	78 ms	10084 KB	Output is correct
18	Correct	89 ms	10104 KB	Output is correct
19	Correct	82 ms	10116 KB	Output is correct
20	Correct	80 ms	10112 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	11168 KB	Output is correct
2	Correct	100 ms	11604 KB	Output is correct
3	Correct	95 ms	11240 KB	Output is correct
4	Correct	98 ms	11116 KB	Output is correct
5	Correct	110 ms	11660 KB	Output is correct
6	Correct	110 ms	11804 KB	Output is correct
7	Correct	101 ms	11568 KB	Output is correct
8	Correct	95 ms	10844 KB	Output is correct
9	Correct	95 ms	10984 KB	Output is correct
10	Correct	97 ms	11144 KB	Output is correct
11	Correct	92 ms	10484 KB	Output is correct
12	Correct	120 ms	11596 KB	Output is correct
13	Correct	96 ms	10436 KB	Output is correct
14	Correct	107 ms	11104 KB	Output is correct
15	Correct	122 ms	12028 KB	Output is correct
16	Correct	105 ms	11808 KB	Output is correct
17	Correct	119 ms	11856 KB	Output is correct
18	Correct	97 ms	10492 KB	Output is correct
19	Correct	136 ms	12300 KB	Output is correct
20	Correct	112 ms	12052 KB	Output is correct
21	Correct	107 ms	11888 KB	Output is correct