Submission #1144609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144609		crafticat	popa (BOI18_popa)	C++20	37 / 100	87 ms	1664 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;

map<tuple<int,int,int,int>, int> cash;

int query(int a, int b, int x, int y);
int query2(int a, int b, int x, int y) {
    if (a < x) {
        swap(a,x);
        swap(b,y);
    }

    if (cash.count({a,b,x,y}))
        return cash[{a,b,x,y}];

    return cash[{a,b,x,y}] = query(a,b,x,y);
}

int search(int l, int r) {
    int testL = l, testR = r;
    bool dir = true;
    int tries = max((int)log2(r - l), 300);
    int space = tries;

    if (r - l >= space * 2) {
        bool s1 = query2(l,l + space - 1, l, r - 1);
        bool s2 = query2(r - space, r - 1, l, r - 1);
        if (s2 and !s1) dir = false;
        if (!s2 and !s2) return -1;
    }

    while (testR > testL and tries-- > 0) {
        if (dir) {
            if (query2(testL, testL, l, r - 1)) {
                return testL;
            }
            testL++;
        } else {
            testR--;
            if (query2(testR, testR, l, r - 1)) {
                return testR;
            }
        }
    }

    return -1;
}

int searchBinary(int a, int b) {
    int l = a, r = b;
    while (l < r) {
        int mid = l + (r - l) / 2; // Including MID
        if (query2(l, mid, a,b - 1)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

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;

    int mid = search(l, r);
    if (mid == -1)
        mid = searchBinary(l, r);

    L[mid] = solve(l, mid, L, R);

    if (mid < r - 1)
        R[mid] = solve(mid + 1, r, L, R);
    else R[mid] = -1;

    return mid;
}

int solve(int N, int* L, int* R) {
    cash.clear();
    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

#if DEBUG2
int queries = 0;
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]);

    queries++;

    return gcd1 == gcd2;
}

int rand(int a, int b) {
    return rand() % (b - a + 1) + a;
}
int myrandom (int i) { return std::rand()%i;}


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

    srand(time(nullptr));

    int tests = 10;
    int bad = 0;
    F0R(i, tests) {
        queries = 0;
        int n = 1000;
        s.resize(n);
        vi p(n);

        FOR(i, 1, n) {
            p[i] = rand(0, i);
        }
        vi prime(1e4, true);
        vi primeList;
        FOR(i, 2, prime.size()) {
            if (!prime[i]) continue;
            primeList.push_back(prime[i]);
            prime[i] = false;

            for (int j = i; j < prime.size(); j+=i) {
                prime[j] = false;
            }
        }

        int iter = 0;
        s[0] = 2;

        FOR(i, 1, n) {
            s[i] = s[p[i]] * primeList[iter++];
        }
        std::random_shuffle ( s.begin(), s.end());


        int* l = new int[n];
        int* r = new int[n];
        solve(n, l, r);
        int stop = 25;


        if (queries > 2000) {
            bad++;
        }
        cout << queries << endl;
    }
    cout << bad;

    return 0;
}
#endif

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