oj.uz

Submission #867599

# Submission time Handle Problem Language Result Execution time Memory
867599 2023-10-28T21:33:38 Z bibinm popa (BOI18_popa) C++17
0 / 100
 7 ms 856 KB 
#include "popa.h"
#include <bits/stdc++.h>

using namespace std;

bool is_anc(int x, int y){
    // gcd(S_x, S_x) == gcd(S_x, S_{x+1}) => S_x | S_{x+1} => x+1 is an ancestor
    return query(x, x, x, y);
}

int solve(int n, int* left, int* right){
    for(int i = 0; i < n; i += 1) left[i] = right[i] = -1;

    vector<int> down_right;
    down_right.push_back(0);

    int cur = 1;
    while(cur < n){
        while(cur < n and !is_anc(down_right.back(), cur)){
            down_right.push_back(cur);
            cur += 1;
        }

        if(cur == n) break;

        int more_down = down_right.back(); down_right.pop_back();
        while(down_right.size() > 0 and is_anc(down_right.back(), cur)){
            right[down_right.back()] = more_down;
            more_down = down_right.back(); down_right.pop_back();
        }

        left[cur] = more_down;

        down_right.push_back(cur);

        cur += 1;
    }


    int more_down = down_right.back(); down_right.pop_back();
    while(down_right.size() > 0){
        right[down_right.back()] = more_down;
        more_down = down_right.back(); down_right.pop_back();
    }

    return more_down;
}

/*
signed main(){
    int n; cin >> n;
    int left[n];
    int right[n];
    solve(n, left, right);
    for(int i = 0; i < n; i += 1) cout << left[i] << " " << right[i] << endl;
}*/

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 436 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 696 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 856 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -