oj.uz

Submission #808647

# Submission time Handle Problem Language Result Execution time Memory
808647 2023-08-05T08:31:30 Z drdilyor Comparing Plants (IOI20_plants) C++17
5 / 100
 100 ms 8884 KB 
#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
using ll = long long;
const int inf = 1e9;

#define debug(args...) cout << "[" << #args << "]: "; debug_out(args);
void debug_out() {
    cout << endl;
}
template<typename H, typename... T>
void debug_out(H h, T... t) {
    cout << h << ", ";
    debug_out(t...);
}

void vis() {
    int n = 7;
    int k = 4;

    vector<int> arr(n);
    iota(arr.begin(), arr.end(), 1);
    map<vector<int>, vector<int>> mp;
    do {
        vector<int> r;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = i; j < i + k; j++)
                cnt += arr[j % n] > arr[i];
            r.push_back(cnt);
        }
        mp[r] = arr;
    }while (next_permutation(arr.begin(), arr.end()));
    for (auto[r, arr] : mp) {
        for (int i : r) cout << i << ' ';
        cout << "= ";
        for (int i : arr) cout << i << ' ';
        cout << endl;
    }

	return;
}

int n;
vector<pair<int,bool>> shape;
int valley = 0;
int peak = 1;

int f(int i) {
    return i < 0 ? i + n : i >= n ? i - n : i;
}

void init(int k, std::vector<int> r) {
    n = r.size();
    assert(k == 2);
    auto rr = r;
    for (int i : rr) r.push_back(i);
    for (int i : rr) r.push_back(i);
    for (int i : rr) r.push_back(i);

    for (int i = n; i < n+n+n; i++) {
        if (r[i-1] == 1 && r[i] == 0) {
            shape.emplace_back(i, peak);
        } else if (r[i-1] == 0 && r[i] == 1) {
            shape.emplace_back(i, valley);
        }
    }
}


int compare_plants(int x, int y) {
    x += n;
    y += n;
    bool inv = false;
    if (x > y) {
        swap(x, y);
        inv = true;
    }

    auto getans = [&]() {
        auto it = lower_bound(shape.begin(), shape.end(), pair{x+1, false});
        if (it->first < y) {
            return 0;
        }
        int ans = it->second == valley ? 1 : -1;
        if (inv) ans *= -1;
        return ans;
    };
    if (getans()) return getans();
    swap(x, y);
    inv ^= true;
    y += n;
    return getans();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 49 ms 3668 KB Output is correct
7 Correct 78 ms 3884 KB Output is correct
8 Correct 91 ms 8884 KB Output is correct
9 Correct 81 ms 8124 KB Output is correct
10 Correct 74 ms 8088 KB Output is correct
11 Correct 100 ms 8100 KB Output is correct
12 Correct 61 ms 8092 KB Output is correct
13 Correct 60 ms 8060 KB Output is correct
14 Correct 59 ms 8108 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 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 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 340 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 340 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 49 ms 3668 KB Output is correct
7 Correct 78 ms 3884 KB Output is correct
8 Correct 91 ms 8884 KB Output is correct
9 Correct 81 ms 8124 KB Output is correct
10 Correct 74 ms 8088 KB Output is correct
11 Correct 100 ms 8100 KB Output is correct
12 Correct 61 ms 8092 KB Output is correct
13 Correct 60 ms 8060 KB Output is correct
14 Correct 59 ms 8108 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Runtime error 1 ms 340 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -