Submission #863959

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
863959	2023-10-21T14:53:56 Z	Ariadna	Finding Routers (IOI20_routers)	C++14	77.9296 / 100	3 ms	1112 KB

routers

#include <bits/stdc++.h>
 
using namespace std;
 
int use_detector(int x);

unordered_map < int, int > ans;

int query(int x) {
    if (ans.find(x) != ans.end()) return ans[x];
    return ans[x] = use_detector(x);
}

int detector(int l, int r, int router) {
    int low = r, hi = l;
    while (low < hi) {
        int m = (low + hi) / 2;
        if (query(m) >= router) hi = m;
        else low = m + 1;
    }
    return low;
}

vector < int > find_routers(int l, int n, int q) {
    vector < int > p(n);
    p[0] = 0;
    for (int i = 1; i < n; ++i) {
        p[i] = 2 * (detector(l, p[i - 1], i) - 1) - p[i - 1];
    }
    return p;
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	432 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	432 KB	Output is correct
8	Correct	0 ms	600 KB	Output is correct
9	Correct	0 ms	436 KB	Output is correct
10	Correct	1 ms	436 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	432 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct

Subtask #4

17.9296 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3 ms	856 KB	Partial score
2	Partially correct	2 ms	856 KB	Partial score
3	Partially correct	2 ms	860 KB	Partial score
4	Partially correct	2 ms	860 KB	Partial score
5	Partially correct	2 ms	860 KB	Partial score
6	Partially correct	2 ms	860 KB	Partial score
7	Partially correct	2 ms	860 KB	Partial score
8	Partially correct	2 ms	856 KB	Partial score
9	Partially correct	2 ms	1112 KB	Partial score
10	Partially correct	2 ms	860 KB	Partial score
11	Partially correct	1 ms	604 KB	Partial score
12	Partially correct	2 ms	860 KB	Partial score
13	Correct	1 ms	348 KB	Output is correct
14	Partially correct	2 ms	860 KB	Partial score
15	Partially correct	2 ms	860 KB	Partial score
16	Partially correct	2 ms	860 KB	Partial score
17	Partially correct	2 ms	860 KB	Partial score
18	Partially correct	3 ms	860 KB	Partial score
19	Partially correct	2 ms	860 KB	Partial score
20	Partially correct	2 ms	860 KB	Partial score
21	Partially correct	2 ms	860 KB	Partial score