Submission #1179826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179826		pcheloveks	popa (BOI18_popa)	C++20	61 / 100	88 ms	464 KiB

popa

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

#include "popa.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };

FILE* stream;

ll findGCD(ll L, ll R, bool prev) {
    if (L == R) return L;
    ll mid = (L + R) / 2;

    if (!prev) {
        if (query(L, mid, L, R)) return findGCD(L, mid, true);
        else return findGCD(mid + 1, R, false);
    }
    else {
        if (query(mid + 1, R, L, R)) return findGCD(mid + 1, R, false);
        else return findGCD(L, mid, true);
    }
}

bool pr = false;
ll buildSubTree(ll L, ll R, int* Left, int* Right) {
    if (L == R) {
        Left[L] = -1;
        Right[L] = -1;
        return L;
    }
    if (L > R) return -1;
    ll root = findGCD(L, R, pr);
    pr ^= 1;

    Left[root] = buildSubTree(L, root - 1, Left, Right);
    Right[root] = buildSubTree(root + 1, R, Left, Right);

    return root;
}

int solve(int N, int* Left, int* Right) {
    return buildSubTree(0, N - 1, Left, Right);
}

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

    //freopen_s(&stream, "input.txt", "r", stdin);
    //freopen_s(&stream, "output.txt", "w", stdout);

    return 0;
}
*/

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