Submission #629437

#	Time	Username	Problem	Language	Result	Execution time	Memory
629437		study	Rarest Insects (IOI22_insects)	C++17	53.48 / 100	157 ms	336 KiB

insects

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

int min_cardinality(int N) {
	vector<int> a(N);
	for (int i=0; i<N; ++i){
		a[i] = i;
	}
//	random_shuffle(a.begin(),a.end());
	bitset<2000> inside;
	int nbElems = 0;
	for (int i=0; i<N; ++i){
		move_inside(a[i]);
		if (i != 0){
			int maxFreq = press_button();
			if (maxFreq > 1) move_outside(a[i]);
			else{
				++nbElems;
				inside[a[i]] = true;
//				cout << a[i] << endl;
			}
		}
		else{
			++nbElems;
			inside[a[i]] = true;
//			cout << a[i] << endl;
		}
	}
	if (nbElems == 1) return N;
	if (nbElems == N) return 1;
	int in = nbElems, crt = 1;
	int deb = 2, fin = N/nbElems, ans = 1;
	vector<int> last;
	while (deb <= fin){
		int mid = fin-(fin-deb)/3.4;
		if (crt > mid) mid = deb+(fin-deb)/3.4;
		bool ok = false;
		if (crt > mid){
/*			for (int i:last){
				inside[i] = false;
				in--;
				move_outside(i);
			}
*/			for (int i=0; i<crt-mid; ++i){
				if (last.empty()) break;
				inside[last.back()] = false;
				move_outside(last.back());
				last.pop_back();
				in--;
			}
			bool yes = false;
			int cnt = 0;
//			random_shuffle(last.begin(),last.end());
			while (!last.empty()){
				int sqrt_siz = sqrt((int)last.size());
				if (cnt%40 == 0 and press_button() <= mid){
					yes = true;
					break;
				}
				++cnt;
				int l = last.back();
				move_outside(l);
				inside[l] = false;
				last.pop_back();
				in--;
			}
//			if (last.empty() and press_button() > mid) return ans;
			if (in == nbElems*mid and yes){
				ok = true;
			}
			crt = mid;
		}
		else last.clear();
		int delta = mid-crt;
		if (!ok){
//			random_shuffle(a.begin(),a.end());
			vector<int> idx;
			for (int i=0; i<N; ++i){
				if (inside[a[i]]) continue;
				--delta;
				if (delta >= 0){
					inside[a[i]] = true;
					move_inside(a[i]);
					++in;
					last.emplace_back(a[i]);
					continue;
				}
				idx.emplace_back(a[i]);
			}
			int siz = idx.size();
			for (int i=0; i<idx.size(); i += sqrt(siz)){
				int add = min((int)sqrt(siz),mid*nbElems-in);
				for (int j=i; j<min((int)idx.size(),i+add); ++j){
					move_inside(idx[j]);
					inside[idx[j]] = true;
					++in;
				}
				crt = press_button();
	//			cout << mid*nbElems-in << ' ' << mid << ' ' << crt << endl;
				int place = i;
				while (crt > mid){
					move_outside(idx[place]);
					inside[idx[place]] = false;
					--in;
					place++;
					crt = press_button();
				}
	//			cout << mid*nbElems-in << ' ' << mid << ' ' << crt << endl;
				for (int j=place; j<=min((int)idx.size(),i+add)-1; ++j) last.emplace_back(idx[j]);
				if (in == mid*nbElems and crt == mid){
					ok = true;
					break;
				}
				for (int j=min((int)idx.size(),i+add); j<min((int)idx.size(),i+(int)sqrt(siz)); ++j){
					move_inside(idx[j]);
					++in;
					crt = press_button();
					if (in == mid*nbElems and crt == mid){
						ok = true;
						inside[idx[j]] = true;
						last.emplace_back(idx[j]);
//						cout << crt << ' ' << in << endl;
						break;
					}
//					cout << mid*nbElems-in << ' ' << mid << ' ' << crt << endl;
					if (crt > mid){
						move_outside(idx[j]);
						--in;
						--crt;
					}
					else{
//						cout << a[i] << ' ' << in << endl;
						inside[idx[j]] = true;
						last.emplace_back(idx[j]);
					}
				}
				if (ok) break;
            for (int j=i; j<place; ++j){
             move_inside(idx[j]);
               ++in;
               crt = press_button();
                if (in == mid*nbElems and crt == mid){
                   ok = true;
                  inside[idx[j]] = true;
                  last.emplace_back(idx[j]);
//                cout << crt << ' ' << in << endl;
                  break;
               }
  //             cout << mid*nbElems-in << ' ' << mid << ' ' << crt << endl;
               if (crt > mid){
                  move_outside(idx[j]);
                  --in;
                 --crt;
               }
               else{
//                cout << a[i] << ' ' << in << endl;
                  inside[idx[j]] = true;
                  last.emplace_back(idx[j]);
               }
            }
			}
		}
//		cout << mid << endl;
		if (ok){
			crt = mid;
			ans = mid;
			deb = mid+1;
		}
		else fin = mid-1;
		crt = mid;
	}
	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:56:9: warning: unused variable 'sqrt_siz' [-Wunused-variable]
   56 |     int sqrt_siz = sqrt((int)last.size());
      |         ^~~~~~~~
insects.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for (int i=0; i<idx.size(); i += sqrt(siz)){
      |                  ~^~~~~~~~~~~

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