oj.uz

Submission #309372

# Submission time Handle Problem Language Result Execution time Memory
309372 2020-10-03T11:24:37 Z georgerapeanu Finding Routers (IOI20_routers) C++17
100 / 100
 4 ms 640 KB 
#include "routers.h"
#include <vector>
#include <algorithm>
#include <map>


using namespace std;

map<int,int> memo;

int my_detector(int pos){
    if(memo.count(pos) == 0){
        memo[pos] = use_detector(pos);
    }

    return memo[pos];
}

void solve(int l,int r,int l_val,int r_val,vector<int> &lst_pos){
    if(l_val > r_val){
        return ;
    }
    if(l == r){
        lst_pos[l_val] = r;
        return ;
    }
    
    int m = (l + r) / 2;
    int tmp = my_detector(m + 1);

    solve(l,m,l_val,tmp - 1,lst_pos);
    solve(m + 1,r,tmp,r_val,lst_pos);
}

vector<int> find_routers(int l, int n, int q) {
	vector<int> ans(n,0);
    vector<int> lst_pos(n,0);
    
    solve(0,l,0,n - 2,lst_pos);

    vector<pair<int,int> > tmp;

    for(int i = 0;i < (int)lst_pos.size();i++){
        tmp.push_back({lst_pos[i],i});
    }

    ans[0] = 0;

    for(int i = 0;i < (int)tmp.size() - 1;i++){
        if(tmp[i].second < tmp[i + 1].second){
            ans[tmp[i + 1].second] = 2 * tmp[i].first - ans[tmp[i].second];
        }
        else{
            ans[tmp[i + 1].second] = 2 * tmp[i].first - ans[tmp[i].second] + 1;
        }
    }

    return ans;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

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

Subtask #4
40.0 / 40.0

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