oj.uz

Submission #418908

# Submission time Handle Problem Language Result Execution time Memory
418908 2021-06-06T08:07:44 Z usachevd0 Comparing Plants (IOI20_plants) C++17
5 / 100
 119 ms 9664 KB 
#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[md(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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 59 ms 3140 KB Output is correct
7 Correct 67 ms 3504 KB Output is correct
8 Correct 119 ms 6740 KB Output is correct
9 Correct 96 ms 6640 KB Output is correct
10 Correct 97 ms 6720 KB Output is correct
11 Correct 112 ms 6640 KB Output is correct
12 Correct 98 ms 9664 KB Output is correct
13 Correct 93 ms 9664 KB Output is correct
14 Correct 96 ms 9656 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 59 ms 3140 KB Output is correct
7 Correct 67 ms 3504 KB Output is correct
8 Correct 119 ms 6740 KB Output is correct
9 Correct 96 ms 6640 KB Output is correct
10 Correct 97 ms 6720 KB Output is correct
11 Correct 112 ms 6640 KB Output is correct
12 Correct 98 ms 9664 KB Output is correct
13 Correct 93 ms 9664 KB Output is correct
14 Correct 96 ms 9656 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Runtime error 1 ms 460 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -