Submission #1137958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137958		ConquerConquerer	popa (BOI18_popa)	C++20	61 / 100	88 ms	472 KiB

popa

#include <bits/stdc++.h>
#include "popa.h"
using namespace std;

/*
int num[1005];

bool query(int x, int y, int u, int v) {
    int P = num[x], Q = num[u];
    for (int i = x + 1; i <= y; i++)
        P = __gcd(P, num[i]);

    for (int i = u + 1; i <= v; i++)
        Q = __gcd(Q, num[i]);

    return (P == Q);
}*/

int a[1005], b[1005];

int backtrack(int L, int R) {
    if (L == R) {
        a[L] = b[L] = -1;
        return L;
    }

    if (L > R) return -1;

    int low = L, high = R;
    while (low < high) {
        int mid = (low + high) >> 1;
        if (query(L, mid, L, R)) high = mid;
            else low = mid + 1;
    }

    a[low] = backtrack(L, low - 1);
    b[low] = backtrack(low + 1, R);
    return low;
}

int solve(int N, int* Left, int* Right) {
    int root = backtrack(0, N - 1);
    for (int i = 0; i < N; i++) {
        Left[i] = a[i];
        Right[i] = b[i];
    }

    return root;
}

/*
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> num[i];

    int A[n], B[n];
    int root = solve(n, A, B);

    cout << "Root " << root << '\n';
    for (int i = 0; i < n; i++)
        cout << A[i] << ' ';
    cout << '\n';

    for (int i = 0; i < n; i++)
        cout << B[i] << ' ';
    cout << '\n';

    return 0;
}*/

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 0 / 39