제출 #303121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303121		tutis	식물 비교 (IOI20_plants)	C++17	5 / 100	111 ms	5984 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
struct ST
{
	int l, r;
	pair<int, int> mn;
	int del = 0;
	ST *left, *right;
	ST(int l, int r, vector<int>&a): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2, a);
			right = new ST((l + r) / 2 + 1, r, a);
			mn = min(left->mn, right->mn);
		}
		else
			mn = {a[l], l};
	}
	void fix()
	{
		if (l == r)
		{
			mn.first += del;
			del = 0;
		}
		else
		{
			mn.first += del;
			left->del += del;
			right->del += del;
			del = 0;
		}
	}
	void add(int x, int y, int w)
	{
		if (x <= l && r <= y)
		{
			del += w;
			return fix();
		}
		fix();
		if (r < x || y < l)
			return;
		left->add(x, y, w);
		right->add(x, y, w);
		mn = min(left->mn, right->mn);
	}
};
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	if (k == 2)
	{
		k0 = k1 = vector<int>(n, 0);
		for (int t = 0; t < 2; t++)
			for (int i = n - 1; i >= 0; i--)
			{
				if (r[i] == 0)
					k0[i] = 1 + k0[(i + 1) % n];
				else
					k1[i] = 1 + k1[(i + 1) % n];
			}
		return;
	}
	if (2 * k > n)
	{
		ST medis(0, n - 1, r);
		auto add = [&](int x, int y, int w)
		{
			while (y >= n)
			{
				x -= n;
				y -= n;
			}
			while (x < 0)
			{
				x += n;
				y += n;
			}
			if (y < n)
			{
				medis.add(x, y, w);
			}
			else
			{
				medis.add(x, n - 1, w);
				medis.add(0, y - n, w);
			}
		};
		for (int i = 0; i < n; i++)
			if (r[i] == 0)
				add(i + 1, i + k - 1, 1);
		A = vector<int>(n, -1);
		for (int tt = 0; tt < n; tt++)
		{
			int i = medis.mn.second;
			add(i + 1, i + k - 1, -1);
			add(i - (k - 1), i - 1, -1);
			A[i] = tt;
			add(i, i, n + 10000);
			r[i] = n + 100;
		}
		return;
	}
}

int compare_plants(int x, int y)
{
	assert(x < y);
	if (K == 2)
	{
		if (k0[x] >= y - x)
			return 1;
		if (k1[x] >= y - x)
			return -1;
		if (k0[y] >= n - y + x)
			return -1;
		if (k1[y] >= n - y + x)
			return 1;
		return 0;
	}
	if (!A.empty())
	{
		if (A[x] < A[y])
			return 1;
		else
			return -1;
	}
	return 0;
}

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

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:50:13: warning: 'medis.ST::right' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |   right->add(x, y, w);
      |   ~~~~~~~~~~^~~~~~~~~
plants.cpp:73:6: note: 'medis.ST::right' was declared here
   73 |   ST medis(0, n - 1, r);
      |      ^~~~~
plants.cpp:49:12: warning: 'medis.ST::left' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   left->add(x, y, w);
      |   ~~~~~~~~~^~~~~~~~~
plants.cpp:73:6: note: 'medis.ST::left' was declared here
   73 |   ST medis(0, n - 1, r);
      |      ^~~~~

• Subtask 1: 5 / 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