제출 #837425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837425		NothingXD	드문 곤충 (IOI22_insects)	C++17	49.64 / 100	143 ms	524 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e3 + 10;
const int lg = 20;
int l[maxn], r[maxn], cnt[maxn];
vector<int> a, b;
vector<int> idx[maxn];

bool check_empty(int x){
	for (int i = x; i < a.size(); i++){
		if (!idx[i].empty()) return false;
	}
	return true;
}

int min_cardinality(int N) {
	int n = N;
	vector<int> A;
	for (int i = 0; i < n; i++) A.push_back(i);
	for (auto i: A){
		move_inside(i);
		if (press_button() == 2){
			move_outside(i);
			b.push_back(i);
			continue;
		}
		//debug(i);
		a.push_back(i);
	}
	for (int i = 0; i < a.size(); i++){
		move_outside(a[i]);
	}
	for (int i = 0; i < b.size(); i++){
		l[i] = -1, r[i] = a.size() - 1;
		if (l[i] + 1 < r[i]){
			int mid = (l[i] + r[i]) >> 1;
			idx[mid].push_back(i);
		}
	}
	//debug(a.size(), b.size());
	while(!check_empty(0)){
		for (int j = 0; j < a.size(); j++){
			move_inside(a[j]);
			for (auto x: idx[j]){
				move_inside(b[x]);
			//	debug(j, x, b[x], press_button());
				if (press_button() == 2) r[x] = j;
				else l[x] = j;
				if (l[x] + 1 < r[x]){
					int mid = (l[x] + r[x]) >> 1;
					idx[mid].push_back(x);
				}
				move_outside(b[x]);
			}
			idx[j].clear();
		}
		//for (int i = 0; i < b.size(); i++) debug(i, l[i], r[i]);
		for (int j = 0; j < a.size(); j++){
			move_outside(a[j]);
		}
	}

	for (int i = 0; i < b.size(); i++){
		cnt[r[i]]++;
	}
	int ans = n;
	for (int i = 0; i < a.size(); i++){
		ans = min(ans, cnt[i]);
	//	debug(cnt[i]);
	}
	return ans+1;
}

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

insects.cpp: In function 'bool check_empty(int)':
insects.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = x; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int j = 0; j < a.size(); j++){
      |                   ~~^~~~~~~~~~
insects.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int j = 0; j < a.size(); j++){
      |                   ~~^~~~~~~~~~
insects.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

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