oj.uz

Submission #385701

# Submission time Handle Problem Language Result Execution time Memory
385701 2021-04-04T18:43:22 Z taulant Finding Routers (IOI20_routers) C++14
100 / 100
 7 ms 1132 KB 
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;

int use_detector(int);

vector<int> find_routers(int l, int n, int q){
 set<pii> s;
 s.insert({0,0});
 s.insert({n,l});
 map<int, int> m;
 vector<int> ret(n); // ret[0] = 0
 for(int i = 1; i < n; ++i){
  int lo = ret[i-1], hi = l;
  auto ir = s.lower_bound({i, 0}), il = ir;
  --il;
  lo = max(lo, il -> second), hi = min(hi, ir -> second);
  while(lo < hi){
   int mid = (lo + hi + 1) / 2;
   int x = m.count(mid)? m[mid] : use_detector(mid);
   s.insert({x, mid});
   m[mid] = x;
   if(x < i) lo = mid;
   else hi = mid - 1;
  }
  ret[i] = lo + lo - ret[i-1];
 }
 return ret;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

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

Subtask #4
40.0 / 40.0

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