제출 #633173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633173		Joshua_Andersson	드문 곤충 (IOI22_insects)	C++17	83.97 / 100	102 ms	556 KiB

insects

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


typedef pair<int, int> p2;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<p2> vp2;

#define rep(var,high) for(int var=0;var<high;var++)
#define repe(var,container) for(auto& var : container)

#define local 0

#if local
int N = 8;
map<int, int> insidemachine;
bool hasinit = false;
vi bois(N);
void init()
{
	return;
	if (hasinit) return;
	hasinit = true;
	//rep(i, N) bois[i] = rand() % N;
	bois[0] = 1;
	bois[1] = 1;
	bois[2] = 1;
	bois[3] = 2;
	bois[4] = 2;
	bois[5] = 2;
	bois[6] = 2;
	bois[7] = 2;
}
void move_inside(int i) { init(); insidemachine[bois[i]]++; }
void move_outside(int i) { if (insidemachine[bois[i]]) insidemachine[bois[i]]--; }
int press_button()
{
	int ret = 0;
	repe(el, insidemachine)	ret = max(ret, el.second);
	return ret;
}

int judgeans()
{
	int ret = 100000000;
	repe(el, insidemachine)	if (el.second!=0) ret = min(ret, el.second);
	return ret;
}
#else
void move_inside(int i);
void move_outside(int i);
int press_button();
#endif


int min_cardinality(int n)
{


	int col = 0;

	vi inside(n);

	int types = 0;

	rep(i, n)
	{
		
		move_inside(i);
		inside[i] = true;
		types++;

		if (press_button() > 1)
		{
			move_outside(i);
			inside[i] = false;
			types--;
		}
	}
	rep(i, n) if (inside[i]) move_outside(i);
	if (types == 1) return n;

	int high = n;
	int low = 1;

	vi isinside(n);
	int insidemaballs = 0;

	set<int> possible;
	rep(i, n) possible.insert(i);

	while (true)
	{
		int x = (high + low) / 2;
		bool works = false;
		if (n>=types*x)
		{
			

			repe(i, possible)
			{
				if (isinside[i]) continue;
				move_inside(i);
				isinside[i] = true;

				insidemaballs++;

				if (press_button() > x)
				{
					move_outside(i);
					isinside[i] = false;
					insidemaballs--;
				}

				if (insidemaballs>=types*x)
				{
					break;
				}
			}
			
			if (insidemaballs == types * x) works = true;

			if (works)
			{
				// Keep insects inside
			}
			if (!works)
			{
				rep(i, n)
				{
					if (!isinside[i])
					{
						possible.erase(i);
					}
					else
					{
						move_outside(i);
					}
				}
				isinside = vi(n, false);
				insidemaballs = 0;
			}
		}
		
		

		// If they are all greater than or equal to ans, the answer is larger than x
		
		if (works)
		{
			low = x;
		}
		else
		{
			high = x;
		}

		if (low+1==high)
		{
			return low;
		}
	}

	//return colorcnt[0];
}

#if local
int main()
{
	rep(i, 100000)
	{
		N = 2+rand() % 100;
		//bois = { 2, 0, 0 ,0 ,2 ,0 ,0 };
		//N = bois.size();
		bois=vi(N);
		rep(i, N) bois[i] = rand() % N;
		insidemachine = map<int, int>();

		rep(i, N) insidemachine[bois[i]]++;
		int jans = 100000000;
		repe(el, insidemachine)	if (el.second != 0) jans = min(jans, el.second);
		insidemachine = map<int, int>();
		

		if (min_cardinality(N)!=jans)
		{
			cout << "ligma:; ";
			rep(i, N)
			{
				cout << bois[i] << ", ";
			}
			cout << "\n\n";
			__debugbreak();
		}
	}
}
#endif

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:61:6: warning: unused variable 'col' [-Wunused-variable]
   61 |  int col = 0;
      |      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 58.97 / 75