제출 #420476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420476		idk321	식물 비교 (IOI20_plants)	C++17	0 / 100	2 ms	460 KiB

plants

#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] + k <= n - 1)
            {
                array<int, 2> res2 = {M, -1};
                for (int i = res1[1] + k; i < n; i++)
                {
                    res2 = min(res2, {r[i], i});
                }

            } 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);
            }

            //for (int i : r) cout << i <<  " ";
            //cout << endl;
        }
    }


	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 5 1
0 1 1 0 2
0 1
*/

컴파일 시 표준 에러 (stderr) 메시지

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: 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