Submission #418907

#	Time	Username	Problem	Language	Result	Execution time	Memory
418907		usachevd0	Comparing Plants (IOI20_plants)	C++17	0 / 100	75 ms	3492 KiB

plants

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "plants.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& e : v)
        stream << e << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

namespace sol {
    const int maxN = 2e5 + 5;
    int n, k;
    int r[maxN];
    int R[maxN], L[maxN];
    bool full[maxN];

    int md(int i) {
        return (i % n + n) % n;
    }

    bool in_seg(int x, int l, int r) {
        if (l <= r)
            return l <= x && x <= r;
        return x >= l || x <= r;
    }
}

void init(int _k, vector<int> _r) {
    using namespace sol;
    n = _r.size();
    k = _k;
    for (int i = 0; i < n; ++i)
        r[i] = _r[i];
    
    assert(k == 2);
    int i0 = -1;
    for (int i = 0; i < n; ++i)
        if (r[i] == 1 && r[md(i - 1)] == 0) {
            i0 = i;
            break;
        }
    assert(i0 != -1);
    L[i0] = R[i0] = i0;
    int i = md(i0 + 1);
    do {
        if (r[md(i - 1)] == 1) {
            L[i] = L[md(i - 1)];
        } else {
            L[i] = i;
        }
        
        i = md(i + 1);
    } while (i != i0);
    i = md(i0 - 1);
    do {
        if (r[i] == 0) {
            R[i] = R[i + 1];
        } else {
            R[i] = i;
        }
        i = md(i - 1);
    } while (i != i0);
    for (int i = 0; i < n; ++i)
        full[i] = L[i] == R[i] && L[i] != i;
}

int compare_plants(int x, int y) {
    using namespace sol;
    // auto greater = [&](int a, int b) -> bool {
    //     int i = a;
    //     while (true) {
    //         if (i == b) return true;
    //         if (r[md(i - 1)] == 1)
    //             i = md(i - 1);
    //         else
    //             break;
    //     }
    //     i = a;
    //     while (true) {
    //         if (i == b) return true;
    //         if (r[i] == 0)
    //             i = md(i + 1);
    //         else
    //             break;
    //     }
    //     return false;
    // };
    // if (greater(x, y)) return +1;
    // if (greater(y, x)) return -1;
    // return 0;
    if (full[x] || in_seg(y, L[x], R[x]))
        return +1;
    if (full[y] || in_seg(x, L[y], R[y]))
        return -1;
    return 0;
}


#ifdef LOCAL

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
    freopen("in", "r", stdin);
    assert(scanf("%d%d%d", &n, &k, &q) == 3);
    r.resize(n);
    answer.resize(q);
    for (int i = 0; i < n; i++) {
        int value;
        assert(scanf("%d", &value) == 1);
        r[i] = value;
    }
    x.resize(q);
    y.resize(q);
    for (int i = 0; i < q; i++) {
        assert(scanf("%d%d", &x[i], &y[i]) == 2);
    }
    fclose(stdin);

    init(k, r);
    for (int i = 0; i < q; i++) {
        answer[i] = compare_plants(x[i], y[i]);
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", answer[i]);
    }

    fclose(stdout);

    return 0;
}


// int32_t main() {
//     #ifdef LOCAL
//         freopen("in", "r", stdin);
//     #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    
    
    
//     return 0;
// }
#endif

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25