제출 #635482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635482		TheLostCookie	Rarest Insects (IOI22_insects)	C++17	10 / 100	432 ms	308 KiB

insects

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

typedef vector<int> vi;

#define FOR(i,a,b) for(int i = (a); i<(b); ++i)
#define all(v) begin(v),end(v)
#define pb push_back

int min_cardinality(int N) {
	vi types;
	vi currSet(N);
	iota(all(currSet),0);
	
	int ans = 0;
	vi nextSet;
	FOR(i,0,currSet.size()) {
		int c = currSet[i];
		move_inside(c);
		if(press_button() > 1) {
			move_outside(c);
			nextSet.pb(c);
		} else {
			types.pb(c);
		}
	}
	FOR(i,0,types.size()) {
		int c = types[i];
		move_outside(c);
	}
	currSet.swap(nextSet);
	ans++;
	
	int t = types.size();
	assert(currSet.size() == N-t);
	
	vector<int> dp(N-t+1,(1<<30));
	vector<int> argMin(N-t+1,-1);
	
	FOR(i,0,min(t,N-t+1)) {
		dp[i] = 0;
		argMin[i] = 0;
	}
	FOR(i,t,min(2*t,N-t+1)) {
		dp[i] = i;
		argMin[i] = t;
	}
	FOR(i,2*t,min(3*t,N-t+1)) {
		dp[i] = i+t;
		argMin[i] = 2*t;
	}
	FOR(i,3*t,N-t+1) {
		int top = i-t, bot = t;
		while(top > 0) {
			int choice = i+min(dp[bot-1]-argMin[bot-1]/t,dp[top]);
			if(choice <= dp[i]) {
				dp[i] = choice;
				argMin[i] = bot;
			}
			top -= t, bot += t;
		}
	}
	
	FOR(i,0,N-t+1) assert(dp[i] <= 2*N);
	
	bool currSetInside = false;
	while(!currSet.empty()) {
		if(currSet.size() < t) {
			currSet.clear();
		} else {
			vi top, bot;
			int m = currSet.size();
			if(currSetInside) {
				FOR(i,0,argMin[m]/t) {
					int c = currSet[i];
					bot.pb(c);
				}
				FOR(i,argMin[m]/t,m) {
					int c = currSet[i];
					move_outside(c);
				}
			}
			FOR(i,(currSetInside?(argMin[m]/t):(0)),m) {
				int c = currSet[i];
				move_inside(c);
				if(press_button() > argMin[m]/t) {
					move_outside(c);
					top.pb(c);
				} else {
					bot.pb(c);
				}
			}
			assert(top.size() + bot.size() == m);
			if(bot.size() == argMin[m]) {
				currSet.swap(top);
				ans += argMin[m]/t;
				FOR(i,0,bot.size()) {
					move_outside(bot[i]);
				}
				currSetInside = false;
			} else {
				if(m < 2*t || m >= 3*t) {
					currSet.swap(bot);
					currSetInside = true;
				} else {
					assert(argMin[m] == 2*t);
					//Microoptimization for 2*t <= n < 3*t
					int twos = 0;
					FOR(i,0,t) {
						move_inside(types[i]);
						if(press_button() > 2) {
							twos++;
						}
						move_outside(types[i]);
					}
					if(twos+t == bot.size()) {
						ans++;
					} else {
						assert(twos > bot.size()%t);
					}
					currSet.clear();
				}
			}
		}
	}
	
	return ans;
}

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:7:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,a,b) for(int i = (a); i<(b); ++i)
      |                                      ^
insects.cpp:18:2: note: in expansion of macro 'FOR'
   18 |  FOR(i,0,currSet.size()) {
      |  ^~~
insects.cpp:7:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,a,b) for(int i = (a); i<(b); ++i)
      |                                      ^
insects.cpp:28:2: note: in expansion of macro 'FOR'
   28 |  FOR(i,0,types.size()) {
      |  ^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from insects.cpp:1:
insects.cpp:36:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  assert(currSet.size() == N-t);
      |         ~~~~~~~~~~~~~~~^~~~~~
insects.cpp:69:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |   if(currSet.size() < t) {
      |      ~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from insects.cpp:1:
insects.cpp:94:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |    assert(top.size() + bot.size() == m);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
insects.cpp:95:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   95 |    if(bot.size() == argMin[m]) {
insects.cpp:7:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,a,b) for(int i = (a); i<(b); ++i)
      |                                      ^
insects.cpp:98:5: note: in expansion of macro 'FOR'
   98 |     FOR(i,0,bot.size()) {
      |     ^~~
insects.cpp:117:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |      if(twos+t == bot.size()) {
      |         ~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from insects.cpp:1:
insects.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       assert(twos > bot.size()%t);
      |              ~~~~~^~~~~~~~~~~~~~

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