Submission #630906

#	Time	Username	Problem	Language	Result	Execution time	Memory
630906		MateGiorbelidze	Rarest Insects (IOI22_insects)	C++17	54.74 / 100	163 ms	340 KiB

insects

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

#define ll long long
#define pb push_back
#define ff first
#define sc second

int n;

int min_cardinality(int N) {
	n = N;
	
	move_inside(0);
	
	vector <int> a , b;
	a.pb(0);
	
	for (int i = 1; i < n; i++) {
		
		move_inside(i);
		
		int ans = press_button();
		 
		if (ans == 2) {
			
			move_outside(i);
			b.pb(i);
			
		}
		else a.pb(i);
		
	}
	
	if (a.size() > b.size()) return 1;
	
	int fr[a.size() + 1];
	
	pair<int,int> d[b.size()];
	
	for (int i = 0; i < b.size(); i++)
		d[i] = {0 , a.size() - 1};
	
	for (int i = 0; i < a.size(); i++)
		fr[i] = 1;
	
	stack < pair<int,int> > st;
	int l = 0, r = a.size() - 1;
	st.push({0 , a.size() - 1});
	
	while (!st.empty()) {
		
		pair<int,int> k = st.top();
		st.pop();
		
		if (k.ff == k.sc) {
			
			for (int i = 0; i < b.size(); i++) {
				
				if (d[i] == k) {
					
					fr[k.ff]++;
					
				}
				
			}
			
		}
		else {
			
			int m = (k.ff + k.sc) / 2;
			
			for (int i = k.ff; i < l; i++)
				move_inside(a[i]);
			
			for (int i = l; i < k.ff; i++)
				move_outside(a[i]);
				
			for (int i = r + 1; i <= m; i++)
				move_inside(a[i]);
				
			for (int i = m + 1; i <= r; i++)
				move_outside(a[i]);		
			
			int cnt1 = 0 , cnt2 = 0;
				
			for (int i = 0; i < b.size(); i++) {
				
				if (d[i] == k) {
					
					move_inside(b[i]);
					
					int ans = press_button();
					
					if (ans == 2) {
						
						cnt1++;
						
						d[i] = {k.ff , m};
						
					}
					else {
						
						cnt2++;
						
						d[i] = {m + 1 , k.sc};
						
					}
					
					move_outside(b[i]);
					
				}
				
			}
			
			if (cnt2 > 0) st.push({m + 1, k.sc});
			if (cnt1 > 0) st.push({k.ff, m});
			
			l = k.ff; r = k.sc;
			
		}

	}
	int mn = INT_MAX;
	
	for (int i = 0; i < a.size(); i++)
		mn = min(mn , fr[i]);
		
	return mn;	
		
	
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < b.size(); i++)
      |                  ~~^~~~~~~~~~
insects.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
insects.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int i = 0; i < b.size(); i++) {
      |                    ~~^~~~~~~~~~
insects.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for (int i = 0; i < b.size(); i++) {
      |                    ~~^~~~~~~~~~
insects.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~

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