Submission #867599

#	Time	Username	Problem	Language	Result	Execution time	Memory
867599		bibinm	popa (BOI18_popa)	C++17	0 / 100	7 ms	856 KiB

popa

#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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39