oj.uz

답안 #1042552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042552 2024-08-03T07:04:36 Z Alihan_8 드문 곤충 (IOI22_insects) C++17
0 / 100
 88 ms 672 KB 
#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

int min_cardinality(int n) {
	vector <int> p;
	
	for ( int i = 0; i < n; i++ ){
		move_inside(i);
		
		if ( press_button() == 1 ){
			p.pb(i);
		} else{
			move_outside(i);
		}
	}
	
	int k = (int)p.size();
	
	if ( __lg(n / k + 1) >= k ){ // random stuff
		vector <int> us(n);
		
		for ( auto &j: p ){
			move_outside(j);
		} p.clear();
		
		vector <int> f;
		
		while ( !*min_element(all(us)) ){
			int cnt = 0;
			
			for ( int i = 0; i < n; i++ ){
				if ( us[i] ) continue;
				
				move_inside(i);
				
				if ( press_button() == cnt + 1 ){
					cnt += 1; p.pb(i);
				} else{
					move_outside(i);
				}
			}
			
			f.pb(cnt);
			
			for ( auto &x: p ){
				us[x] = 1;
				
				move_outside(x);
			} p.clear();
		}
		
		return *min_element(all(f));
	}
	
	for ( auto &x: p ){
		move_outside(x);
	} p.clear();
	
	vector <int> us(n), tmp, rem;
	
	auto ok = [&](int m){
		int cnt = 0;
		
		tmp = p;
		rem.clear();
		
		for ( int i = 0; i < n; i++ ){
			if ( us[i] ) continue;
			
			move_inside(i);
			
			if ( press_button() > m ){
				move_outside(i);
				
				rem.pb(i);
			} else{
				tmp.pb(i);
				cnt += 1;
			}
		}
		
		return cnt == k * m;
	};
	
	int l = 1, r = n / k + 1;
	
	while ( l + 1 < r ){
		int m = (l + r) / 2;
		
		if ( ok(m) ){
			for ( auto &x: p ){
				us[x] = 1;
			} l = m;
		}
		else{
			for ( auto &x: rem ){
				us[x] = 1;
			} 
			
			for ( auto &x: p ){
				move_outside(x);
			} p.clear();
			
			r = m;
		}
	}
	
	return l;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 19 ms 448 KB Output is correct
8 Correct 11 ms 456 KB Output is correct
9 Partially correct 74 ms 672 KB Output is partially correct
10 Partially correct 62 ms 344 KB Output is partially correct
11 Correct 23 ms 344 KB Output is correct
12 Correct 22 ms 672 KB Output is correct
13 Partially correct 33 ms 592 KB Output is partially correct
14 Correct 24 ms 344 KB Output is correct
15 Partially correct 34 ms 344 KB Output is partially correct
16 Incorrect 88 ms 428 KB Wrong answer.
17 Halted 0 ms 0 KB -