oj.uz

Submission #1042548

# Submission time Handle Problem Language Result Execution time Memory
1042548 2024-08-03T06:52:52 Z Alihan_8 Rarest Insects (IOI22_insects) C++17
10 / 100
 73 ms 664 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;
}

const int C = 100;

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);
		}
	}
	
	if ( (int)p.size() > 100 ){
		int cnt = 0;
		
		vector <int> us(n);
		
		while ( !*min_element(all(us)) ){
			cnt += 1;
			
			int lst = (int)p.size();
			
			for ( auto &j: p ){
				us[j] = 1;
				
				move_outside(j);
			} p.clear();
			
			for ( int i = 0; i < n; i++ ){
				if ( us[i] ) continue;
				
				move_inside(i);
				
				if ( press_button() == 1 ){
					p.pb(i);
				} else{
					move_outside(i);
				}
			}
			
			if ( (int)p.size() != lst ){
				break;
			}
		}
		
		return cnt;
	} else if ( (int)p.size() < 20 ){
		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));
	}
	
	int k = (int)p.size();
	
	for ( auto &x: p ){
		move_outside(x);
	} p.clear();
	
	auto ok = [&](int m){
		int cnt = 0;
		
		for ( int i = 0; i < n; i++ ){
			move_inside(i);
			
			if ( press_button() > m ){
				move_outside(i);
			} else{
				p.pb(i);
				cnt += 1;
			}
		}
		
		for ( auto &x: p ){
			move_outside(x);
		} p.clear();
		
		return cnt == k * m;
	};
	
	int l = 1, r = n / k;
	
	while ( l + 1 < r ){
		int m = (l + r) / 2;
		
		if ( ok(m) ) l = m;
		else r = m;
	}
	
	return l;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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 2 ms 600 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 5 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 436 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory 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 2 ms 600 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 5 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 436 KB Output is correct
23 Correct 8 ms 448 KB Output is correct
24 Correct 4 ms 440 KB Output is correct
25 Incorrect 30 ms 664 KB Wrong answer.
26 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 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 0 ms 344 KB Output is correct
7 Correct 13 ms 444 KB Output is correct
8 Correct 9 ms 600 KB Output is correct
9 Incorrect 73 ms 644 KB Wrong answer.
10 Halted 0 ms 0 KB -