Submission #784913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784913	2023-07-16T18:35:31 Z	Boas	Finding Routers (IOI20_routers)	C++17	89.6128 / 100	1 ms	276 KB

routers

#include "routers.h"
using namespace std;
// l is length
// n is number of routers
// q is max uses of detector
vector<int> find_routers(int l, int n, int q)
{
  vector<int> ans(n); // distance of each router i to the origin
  if (n == 2)
  {
    // find position of switch (first point where i = 1) using binary search
    int min = 2;
    int max = (l / 2) + 1;
    while (max - min > 0)
    {
      int k = (max + min) / 2;
      int i = use_detector(k);
      if (i == 0)
      {
        min = k + 1;
      }
      else
      {
        max = k;
      }
    }
    if (1 >= ans.size() || 1 < 0)
      throw;
    ans[1] = min + max - 2;
  }
  else
  {
    for (int i = 1; i < n; i++)
    {
      if (i - 1 >= ans.size() || i - 1 < 0)
        throw;
      int locMin = ans[i - 1] + 2;
      int locMax = l - (2 * (n - 1 - i));
      if (locMin == locMax)
      {
        ans[i] = locMin;
        continue;
      }
      int sMin = locMin;
      int sMax = ((ans[i - 1] + locMax) / 2) + 1;
      while (sMax - sMin > 0)
      {
        int k = (sMax + sMin) / 2;
        int diff = sMax - sMin;
        k = sMin + 0.2 * diff; // alternative
        int detectorIndex = use_detector(k);
        if (detectorIndex == i - 1)
        {
          sMin = k + 1;
        }
        else
        {
          sMax = k;
        }
      }
      int mid = sMin - 1;
      ans[i] = mid + (mid - ans[i - 1]);
    }
  }
  return ans;
}

Compilation message

routers.cpp: In function 'std::vector<int> find_routers(int, int, int)':
routers.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |       if (i - 1 >= ans.size() || i - 1 < 0)
      |           ~~~~~~^~~~~~~~~~~~~

Subtask #1

16.0 / 16.0

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

Subtask #2

21.0 / 21.0

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

Subtask #3

23.0 / 23.0

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

Subtask #4

29.6128 / 40.0

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