oj.uz

답안 #1052518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052518 2024-08-10T15:36:06 Z dozer 버섯 세기 (IOI20_mushrooms) C++14
0 / 100
 35 ms 720 KB 
#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 300005
#define LOGN 16

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


int count_mushrooms(int n) {
	vector<int> done(n, 0);
	done[0] = 1;
	int ans = 1;
	vector<int> as;
	as.pb(0);

	int pos = 0;
	for (int i = 1; i <= 3; i++){
		if (pos == n - 1) return ans;
		vector<int> tmp = {pos, pos + 1};
		int sum = use_machine(tmp);
		if (sum == 0){
			as.pb(pos + 1);
			done[pos + 1] = 1;
			pos++;
			ans++;
			continue;
		}


		for (int j = LOGN; j >= 0; j--){
			vector<int> gh;
			int tmp = pos + (1<<j);
			if (tmp >= n) continue;
			gh.pb(0);
			for (int k = pos + 1; k <= tmp; k++) gh.pb(k);
			
			int ga = use_machine(gh);
			if (ga == 1) {
				pos = tmp;
				done[pos] = 1;
			}
		}
		pos++;
		if (pos == n) return ans;
		done[pos] = 1;
		ans++;
		as.pb(pos);
	}


	vector<int> undone;
	for (int i = 0; i < n; i++) if (done[i] == 0) undone.pb(i);

	while(!undone.empty()){
		vector<int> curr;
		curr.pb(as[0]);
		int sum = 0;
		for (int i = 1; i <= 3; i++){
			if (!undone.empty()){
				curr.pb(undone.back());
				undone.pop_back();
				sum++;
			}
			curr.pb(as[i]);
		}
		int res = use_machine(curr);
		res /= 2;
		ans += sum - res;
	}

	return ans;
}

/*
static char fmt_buffer[100000];
#define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
	vsnprintf(fmt_buffer, sizeof(fmt_buffer), fmt, vargs); \
	va_end(vargs); fmt_buffer[sizeof(fmt_buffer)-1] = 0; \
	std::string result(fmt_buffer);

static const int min_n = 2;
static const int max_n = 20000;
static const int max_qc = 20000;
static const int max_qs = 100000;
static const int species_A = 0;
static const int species_B = 1;

static int n;
static std::vector<int> species;
static int qc, qs;

static inline void error_if(bool cond, std::string message) {
	if (cond) {
		printf("%s\n", message.c_str());
		exit(0);
	}
}

static inline void wrong_if(bool cond, std::string message) {
	error_if(cond, "Wrong Answer: "+message);
}

int use_machine(std::vector<int> x) {
	const int xs = x.size();
	wrong_if(xs < 2, "Too small array for query.");
	wrong_if(xs > n, "Too large array for query.");
	qc++;
	wrong_if(qc > max_qc, "Too many queries.");
	qs += xs;
	wrong_if(qs > max_qs, "Too many total array sizes as queries.");
	for (int i = 0; i < xs; i++)
		wrong_if(x[i] < 0 || n - 1 < x[i], "Invalid value in the query array.");
	std::vector<bool> used(n, false);
	for (int i = 0; i < xs; i++) {
		wrong_if(used[x[i]], "Duplicate value in the query array.");
		used[x[i]] = true;
	}
	int diffs = 0;
	for (int i = 1; i < xs; i++)
		diffs += int(species[x[i]] != species[x[i-1]]);
	return diffs;
}

#ifdef __GNUC__
__attribute__ ((format(printf, 2, 3)))
#endif
static inline void check_input(bool cond, const char* message_fmt, ...) {
	FMT_TO_STR(message_fmt, message);
	error_if(!cond, "Invalid input: "+message);
}

int main() {
	fileio();
	check_input(1 == scanf("%d", &n), "Could not read n.");
	check_input(min_n <= n, "n must not be less than %d, but it is %d.", min_n, n);
	check_input(n <= max_n, "n must not be greater than %d, but it is %d.", max_n, n);
	species.resize(n);
	for (int i = 0; i < n; i++) {
		check_input(1 == scanf("%d", &species[i]), "Could not read species element [%d].", i);
		check_input(species[i]==species_A || species[i] == species_B,
					"Species elements must be %d or %d, but species element [%d] is %d.", species_A, species_B, i, species[i]);
	}
	check_input(species[0] == species_A, "Species element [%d] must be %d.", 0, species_A);
	// Postponed closing standard input in order to allow interactive usage of the grader.

	qc = 0;
	qs = 0;
	int answer = count_mushrooms(n);
	printf("%d\n%d\n", answer, qc);
	fclose(stdout);
	fclose(stdin);
	return 0;
}*/

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 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 Partially correct 3 ms 344 KB Output is partially correct
7 Partially correct 30 ms 708 KB Output is partially correct
8 Partially correct 35 ms 708 KB Output is partially correct
9 Partially correct 34 ms 704 KB Output is partially correct
10 Partially correct 28 ms 712 KB Output is partially correct
11 Partially correct 23 ms 712 KB Output is partially correct
12 Incorrect 31 ms 720 KB Too many total array sizes as queries.
13 Halted 0 ms 0 KB -