Submission #1144453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144453		crafticat	popa (BOI18_popa)	C++20	61 / 100	58 ms	624 KiB

popa

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

#define F0R(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b - 1;i>=a;i--)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;
const int INF=1e9+7;

int query(int a, int b, int x, int y);

int solve(int l, int r, int* L, int* R) {
    if (r - l == 1) {
        L[l] = -1;
        R[l] = -1;
        return l;
    }
    if (r - l == 0) return -1;

    vi imp;
    int testL = l, testR = r;
    bool dir = true;

    while (testR > testL) {
        if (dir) {
            if (query(testL, testL, l, r - 1)) {
                imp.push_back(testL);
                break;
            }
            testL++;
        } else {
            testR--;
            if (query(testR, testR, l, r - 1)) {
                imp.push_back(testR);
                break;
            }
        }

        dir = !dir;
    }

    int past = l - 1;

    F0R(i, imp.size()) {
        int x = imp[i];
        L[x] = solve(past + 1, x, L, R);
        R[x] = i == imp.size() - 1 ? -1 : imp[i + 1];

        past = x;
    }

    if (past < r - 1)
        R[imp[imp.size() - 1]] = solve(past + 1, r, L, R);

    return imp[0];
}

int solve(int N, int* L, int* R) {
    return solve(0, N, L, R);
}

#if DEBUG
vi s;
int query(int a, int b, int x, int y) {
    int gcd1 = s[a], gcd2 = s[x];
    FOR(i, a, b + 1)
        gcd1 = gcd(gcd1, s[i]);
    FOR(i, x, y + 1)
        gcd2 = gcd(gcd2, s[i]);

    return gcd1 == gcd2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n; cin >> n;
    s.resize(n);
    F0R(i, n) cin >> s[i];

    int* l = new int[n];
    int* r = new int[n];
    solve(n, l, r);
    int stop = 25;
    F0R(i, n) {
        cout << l[i] << " " << r[i] << endl;
    }

    return 0;
}
#endif

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