oj.uz

답안 #830921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830921 2023-08-19T12:58:07 Z FatihSolak 드문 곤충 (IOI22_insects) C++17
0 / 100
 17 ms 320 KB 
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
	
int min_cardinality(int N){
	mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
	vector<int> ord;
	for(int i = 0;i<N;i++){
		ord.push_back(i);
	}
	shuffle(ord.begin(),ord.end(),rng);
	vector<int> v;
	int now = 0;
	int dif = 0;
	auto add = [&](int x){
		v.push_back(x);
		move_inside(ord[x]);
		now = press_button();
	};
	auto del = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
		now = press_button();
	};
	auto del2 = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
		now--;
	};
	auto del3 = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
	};
	add(0);
	dif = 1;
	for(int i = 1;i<N;i++){
		add(i);
		if(now == 2){
			del2();
		}
		else dif++;
	}
	if(dif <= 3){
		vector<bool> found(N,0);
		int mini = 1e9;
		int rem = N;
		for(int i = 0;i<N && dif > 1;i++){
			if(found[i] == 0){
				dif--;
				while(v.size())
					del3();
				now = 0;
				int cnt = 0;
				for(int j = 0;j<N;j++){
					if(found[j])continue;
					add(j);
					if(now != cnt + 1){
						del3();
					}
					else{
						found[j] = 1;
						cnt++;
						rem--;
					}
				}
				mini = min(mini,cnt);
			}
		}
		mini = min(mini,rem);
		return mini;
	}
	vector<int> ban(N,0);
	int l = 1,r = N/dif;
	int ext = 0;
	while(l < r){
		int num = 0;
		for(int i = 0;i<N;i++){
			num += !ban[i];
		}
		r = min(r,ext + num/dif);
		int m = (l + r + 1)/2;
		if(now < m-ext){
			for(int i = 0;i<N && v.size() == (m-ext) * dif;i++){
				if(ban[i] == 0 && find(v.begin(),v.end(),i) == v.end()){
					add(i);
					if(now > m - ext)
						del2();
				}
			}
		}
		else{
			while(v.size()){
				del3();
			}
			now = 0;
			for(int i = 0;i<N && v.size() == (m-ext) * dif;i++){
				if(ban[i] == 0 && find(v.begin(),v.end(),i) == v.end()){
					add(i);
					if(now > m - ext)
						del2();
				}
			}
		}
		if(v.size() == (m-ext) * dif){
			for(auto u:v){
				ban[u] = 1;
			}
			while(v.size())
				del3();
			now = 0;
			ext = m;
			l  = m;
		}
		else{
			r = m -1;
			for(int i = 0;i<N;i++){
				if(find(v.begin(),v.end(),i) == v.end()){
					ban[i] = 1;
				}
			}
		}
	}
	return l;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:83:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |    for(int i = 0;i<N && v.size() == (m-ext) * dif;i++){
      |                         ~~~~~~~~~^~~~~~~~~~~~~~~~
insects.cpp:96:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |    for(int i = 0;i<N && v.size() == (m-ext) * dif;i++){
      |                         ~~~~~~~~~^~~~~~~~~~~~~~~~
insects.cpp:104:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |   if(v.size() == (m-ext) * dif){
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~
insects.cpp:20:7: warning: variable 'del' set but not used [-Wunused-but-set-variable]
   20 |  auto del = [&](){
      |       ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 2 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 2 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 228 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 15 ms 208 KB Output is correct
8 Correct 15 ms 320 KB Output is correct
9 Incorrect 17 ms 208 KB Wrong answer.
10 Halted 0 ms 0 KB -