oj.uz

Submission #420462

# Submission time Handle Problem Language Result Execution time Memory
420462 2021-06-08T11:32:49 Z idk321 Comparing Plants (IOI20_plants) C++17
5 / 100
 93 ms 6520 KB 
#include "plants.h"

#include <bits/stdc++.h>
using namespace std;

int k;
vector<int> r;
vector<int> prefR;
const int N = 200005;
int tree[4 * N];
int treeInd[4 * N];
int lazy[4 * N];
const int M = 1000000000;


int n;
int getSum(int from, int to)
{
    int res = prefR[to + 1];
    res -= prefR[from];
    return res;
}

void push(int node)
{
    for (int i = 0; i <= 1; i++)
    {
        tree[node * 2 +i] += lazy[node];
        lazy[node * 2 + i] += lazy[node];
    }
    lazy[node] = 0;
}

void add(int num, int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        if (a == b) treeInd[node] = a;
        tree[node] += num;
        lazy[node] += num;
        return;
    }

    push(node);
    int mid = (a + b) / 2;
    if (from <= mid) add(num, from, to, a, mid, node * 2);
    if (to > mid) add(num, from, to, mid + 1, b, node * 2+ 1);

    if (tree[node * 2] <= tree[node * 2 +1])
    {
        treeInd[node] = treeInd[node * 2];
        tree[node] = tree[node * 2];
    } else
    {
        treeInd[node] = treeInd[node * 2 + 1];
        tree[node] = tree[node * 2 + 1];
    }
}

array<int, 2> minIndOn(int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        return {tree[node], treeInd[node]};
    }

    push(node);
    int mid = (a + b) / 2;
    array<int, 2> res = {M, -1};
    if (from <= mid) res = min(res, minIndOn(from, to, a, mid, node  *2));
    if (to > mid) res = min(res, minIndOn(from, to, mid + 1, b, node * 2 + 1));

    return res;
}

vector<int> order;

void init(int K, std::vector<int> R) {
    k = K;
    r = R;
    n = r.size();
    prefR.resize(r.size() + 1);
    for (int i = 1; i <= r.size(); i++)
    {
        prefR[i] = r[i - 1];
        prefR[i] += prefR[i - 1];
    }

    order.resize(n);

    if (2 * k > n)
    {
        /*
        for (int i = 0; i < n; i++)
        {
            add(r[i], i, i, 0, n - 1, 1);
        }   */

        for (int t = 0; t < n; t++)
        {
            array<int, 2> res = {-1, -1};

            array<int,2> res1 = {M, -1};
            for (int i = 0; i < n; i++)
            {
                res1 = min(res1, {r[i], i});
            }
            if (res1[1] != n - 1)
            {
                array<int, 2> res2 = {M, -1};
                for (int i = res1[i] + 1; i < n; i++)
                {
                    res2 = min(res2, {r[i], i});
                }
                if (res2[0] == 0)
                {
                    int dist = res2[1] - res1[1];
                    if (dist < k)
                    {
                        res = res1;
                    } else
                    {
                        res = res2;
                    }
                } else
                {
                    res = res1;
                }
            } else res = res1;


            order[res[1]] = t;
            //add(M, res[1], res[1], 0, n - 1, 1);
            r[res[1]] += M;
            for (int i = max(0, res[1] - k + 1); i < res[1]; i++) r[i]--;
            //if (res[1] != 0) add(-1, max(0, res[1] - k + 1), res[1] - 1, 0, n - 1, 1);
            int still = k - (res[1] - max(0, res[1] - k + 1) + 1);
            for (int i = n - still; i < n; i++) r[i]--;
            if (still > 0)
            {
                //add(-1, n - still, n - 1, 0, n - 1, 1);
            }
        }
    }


	return;
}

int compare_plants(int x, int y) {
    if (k == 2)
    {
        if (getSum(x, y - 1) == (y - x)) return -1;
        if (getSum(x, y - 1) == 0) return 1;
        int sum1 = getSum(y, n -1);
        if (x != 0) sum1 += getSum(0, x - 1);
        if (sum1 == (n - y) + x) return 1;
        if (sum1 == 0) return -1;
        return 0;
    }


    if (order[x] < order[y])
    {
        return 1;
    }
    if (order[x] > order[y]) return -1;

	return 0;
}

//3 2 1 4 0
/*
5 3 1
0 1 1 0 2
0 1
*/

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 1; i <= r.size(); i++)
      |                     ~~^~~~~~~~~~~

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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 61 ms 3028 KB Output is correct
7 Correct 66 ms 3500 KB Output is correct
8 Correct 92 ms 6520 KB Output is correct
9 Correct 91 ms 6480 KB Output is correct
10 Correct 91 ms 6516 KB Output is correct
11 Correct 93 ms 6468 KB Output is correct
12 Correct 91 ms 6496 KB Output is correct
13 Correct 88 ms 6504 KB Output is correct
14 Correct 88 ms 6496 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 Correct 0 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 Incorrect 4 ms 332 KB Output isn't correct
7 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 Correct 0 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 Incorrect 4 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 1 ms 204 KB Output isn't correct
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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 61 ms 3028 KB Output is correct
7 Correct 66 ms 3500 KB Output is correct
8 Correct 92 ms 6520 KB Output is correct
9 Correct 91 ms 6480 KB Output is correct
10 Correct 91 ms 6516 KB Output is correct
11 Correct 93 ms 6468 KB Output is correct
12 Correct 91 ms 6496 KB Output is correct
13 Correct 88 ms 6504 KB Output is correct
14 Correct 88 ms 6496 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 4 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -