oj.uz

Submission #1042551

# Submission time Handle Problem Language Result Execution time Memory
1042551 2024-08-03T07:03:11 Z Alihan_8 Rarest Insects (IOI22_insects) C++17
0 / 100
 92 ms 680 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;
			} r = m;
		}
	}
	
	return l;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 0 ms 344 KB Output is correct
7 Correct 24 ms 596 KB Output is correct
8 Correct 10 ms 600 KB Output is correct
9 Partially correct 85 ms 424 KB Output is partially correct
10 Partially correct 57 ms 600 KB Output is partially correct
11 Correct 21 ms 344 KB Output is correct
12 Correct 20 ms 600 KB Output is correct
13 Partially correct 43 ms 676 KB Output is partially correct
14 Correct 22 ms 436 KB Output is correct
15 Partially correct 40 ms 344 KB Output is partially correct
16 Incorrect 92 ms 680 KB Wrong answer.
17 Halted 0 ms 0 KB -