제출 #434692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434692		frodakcin	식물 비교 (IOI20_plants)	C++11	컴파일 에러	0 ms	0 KiB

plants

#include "plants.h"
#include <queue>
#include <bitset>

namespace SLOW_SOLN
{
	const int MN = 5e3+10;
	const int INF = 0x3f3f3f3f;

	int N, K, ts[MN], ctr;
	bool v[MN];
	std::vector<int> a[MN]; // i > a[i][...] -- dag
	std::bitset<MN> vis[MN];

	void dfs(int n)
	{
		v[n]=1;
		for(int x:a[n])
			if(!v[x])
				dfs(x);
		ts[ctr++]=n;
	}

	void init(int k, std::vector<int> r) {
		K=k, N=r.size();
		
		std::queue<int> q;
		int zc=0;
		for(int i=N-K;i<N;++i)
			zc += !r[i];
		for(int i=0;i<N;++i)
		{
			zc -= !r[(N-K+i)%N];
			if(zc==0 && r[i]==0)
				q.push(i);
			zc += !r[i];
		}

		for(;!q.empty();)
		{
			int n=q.front(); q.pop();
			if(r[n] < 0) continue;
			
			// check
			bool ok=1;
			for(int i=1;i<K;++i)
				if(r[(n-i+N)%N]==0)
					ok=0;
			if(!ok) continue;

			// add
			r[n]=-1;
			for(int i=K-1;i>0;--i)
				--r[(n-i+N)%N];
			for(int i=1;i<K;++i)
				if(r[(n+i)%N] == 0)
				{
					q.push((n+i)%N);
					break;
				}
			for(int i=K-1;i>0;--i)
				if(r[(n-i+N)%N] == 0)
				{
					q.push((n-i+N)%N);
					break;
				}
			for(int i=1;i<K;++i)
				if(r[(n+i)%N] >= 0)
					a[n].push_back((n+i)%N);
			for(int i=1;i<K;++i)
				if(r[(n-i+N)%N] >= 0)
					a[n].push_back((n-i+N)%N);
		}

		for(int i=0;i<N;++i)
			if(!v[i])
				dfs(i);

		for(int i=0;i<N;++i)
			vis[i].set(i);
		for(int i=0;i<N;++i)
			for(int x:a[ts[i]])
				vis[ts[i]]|=vis[x];
		return;
	}

	int compare_plants(int x, int y)
	{
		if(vis[x][y]) return 1;
		if(vis[y][x]) return -1;
		return 0;
	}
}

template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}

const int MN = 2e5+10;
const int INF = 0x3f3f3f3f;

int N, K, ts[MN], ctr, ord[MN];
bool v[MN], done[MN];

//Minmax Segtree
struct minmax
{
	public:
		int min, max;
		minmax(int _mn=INF, int _mx=-INF): min(_mn), max(_mx) {}
		minmax& operator += (const int& o) {min += o, max += o; return *this;}
		minmax& operator -= (const int& o) {min -= o, max -= o; return *this;}
		minmax& operator += (const minmax& o) {ckmin(min, o.min); ckmax(max, o.max); return *this;}

		friend minmax operator + (minmax a, const int& b) {return a+=b;}
		friend minmax operator - (minmax a, const int& b) {return a-=b;}
		friend minmax operator + (minmax a, const minmax& b) {return a+=b;}

		bool contains(int x) {return min <= x && x <= max;}
		bool contains(const minmax& x) {return min <= x.min && x.max <= max;}
} range[MN];
minmax mv[1 << 19];
minmax mqry(int n, int l, int r, int ql, int qr)
{
	if(ql <= l && r <= qr) return mv[n];
	else
	{
		int m=l+(r-l)/2; minmax f;
		if(ql < m) f += mqry(n<<1, l, m, ql, qr);
		if(m < qr) f += mqry(n<<1|1, m, r, ql, qr);
		return f;
	}
}
void mupd(int n, int l, int r, int q, minmax val)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q < m) mupd(n<<1, l, m, q, val);
		else mupd(n<<1|1, m, r, q, val);
		mv[n]=mv[n<<1]+mv[n<<1|1];
	}
	else
		mv[n]=val;
}

//R segment tree
int rv[1 << 19], rz[1 << 19];
void rupd(int n, int x) {rv[n] += x, rz[n] += x;}
void rdown(int n)
{
	if(rz[n])
	{
		rupd(n<<1, rz[n]);
		rupd(n<<1|1, rz[n]);
		rz[n]=0;
	}
}
void rupd(int n, int l, int r, int ql, int qr, int x)
{
	if(ql <= l&&r <= qr) rupd(n, x);
	else
	{
		int m=l+(r-l)/2;
		rdown(n);
		if(ql < m) rupd(n<<1, l, m, ql, qr, x);
		if(m < qr) rupd(n<<1|1, m, r, ql, qr, x);
		rv[n] = std::min(rv[n<<1], rv[n<<1|1]);
	}
}
int rqry(int n, int l, int r, int ql) // return leftmost zero
{
	if(rv[n] > 0) return r;
	else if(r-l>1)
	{
		int m=l+(r-l)/2, f=m;
		rdown(n);
		if(ql < m) f=rqry(n<<1, l, m, ql);
		if(f == m) f=rqry(n<<1|1, m, r, ql);
		return f;
	}
	else return l;
}

void init(int k, std::vector<int> r) {
	K=k, N=r.size();
	if(N <= 5000)
	{
		return slow_soln::init(k, r);
	}
	
	std::queue<int> q;
	int zc=0;
	for(int i=N-K;i<N;++i)
		zc += !r[i];
	for(int i=0;i<N;++i)
	{
		zc -= !r[(N-K+i)%N];
		if(zc==0 && r[i]==0)
			q.push(i);
		zc += !r[i];
	}
	for(int i=0;i<N;++i)
		rupd(1, 0, N, i, i+1, r[i]);

	for(;!q.empty();)
	{
		int n=q.front(); q.pop();
		if(done[n]) continue;
		
		// check
		int loc = rqry(1, 0, N, n-K+1);
		//printf("?? %d (%d)\n", n, loc);
		if(loc < n) continue;
		if(n-K+1 < 0 && rqry(1, 0, N, n-K+1+N) < N) continue;

		// add
		rupd(1, 0, N, n, n+1, INF);
		//printf("TEST [%d] %d\n", n, rqry(1, 0, N, 0));

		rupd(1, 0, N, n-K+1, n, -1);
		if(n-K+1 < 0) rupd(1, 0, N, n-K+1+N, N, -1);

		loc = rqry(1, 0, N, n);
		if(loc < std::min(N, n+K))
			q.push(loc);
		else if(n+K>N)
		{
			loc = rqry(1, 0, N, 0);
			if(loc<n+K-N)
				q.push(loc);
		}

		loc = N;
		if(n-K+1 < 0)
			loc = rqry(1, 0, N, n-K+1+N);
		if(loc < N)
			q.push(loc);
		else
		{
			loc = rqry(1, 0, N, n-K+1);
			if(loc < n)
				q.push(loc);
		}

		//modify ans
		ts[ctr]=n;
		ord[n]=ctr++;
		done[n]=1;
	}

	for(int i=N-1, n;i>=0;--i)
	{
		n=ts[i];
		range[n] = minmax(n, n);
		range[n] += mqry(1, 0, N, n-K+1, n+K);
		if(n+K>N) range[n] += mqry(1, 0, N, 0, n+K-N)+N;
		if(n-K+1<0) range[n] += mqry(1, 0, N, n-K+1+N, N)-N;
		mupd(1, 0, N, n, range[n]);
		//printf("%d: %d <-> %d\n", n, range[n].min, range[n].max);
	}
	return;
}

bool cover(int a, int b) // is a > b?
{
	if(ord[a]>ord[b]) return 0;
	return range[a].contains(range[b]) || range[a].contains(range[b]+N) || range[a].contains(range[b]-N);
}

int compare_plants(int x, int y)
{
	if(N <= 5000)
	{
		return slow_soln::compare_plants(x, y);
	}
	if(cover(x, y)) return 1;
	if(cover(y, x)) return -1;
	return 0;
}

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

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:188:10: error: 'slow_soln' has not been declared
  188 |   return slow_soln::init(k, r);
      |          ^~~~~~~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:274:10: error: 'slow_soln' has not been declared
  274 |   return slow_soln::compare_plants(x, y);
      |          ^~~~~~~~~