Submission #661225

#	Time	Username	Problem	Language	Result	Execution time	Memory
661225		perchuts	Counting Mushrooms (IOI20_mushrooms)	C++17	90.76 / 100	8 ms	356 KiB

mushrooms

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "mushrooms.h"
using namespace std;

template<typename X,typename Y> bool ckmin(X& x,Y y){return (x>y?x=y,1:0);}

using ii = pair<int,int>;

int use_machine(vector<int> x);

int count_mushrooms(int n){
    vector<int>m;
    vector<vector<int>>v(2,vector<int>());

    int k = (n<=500?100:50), x, y, type = 0;
    
    if(n<=226){ 
        int ans = 1;
        for(int i=1;i<n;++i)ans += (1 - use_machine({0,i}));
        return ans;
    }

    v[0].pb(0);

    int r1 = use_machine({0,1}), r2 = use_machine({0,2});

    if(r1)v[1].pb(1);
    else v[0].pb(1);

    if(r2)v[1].pb(2);
    else v[0].pb(2);


    if(!r1)x = 0, y = 1;
    else if(!r2)x = 0, y = 2;    
    else x = 1, y = 2, type = 1;

    for(int i=3;i<2*k-1;i+=2){
        assert(i+1<n);
        int cur = use_machine({i,x,i+1,y});

        if(cur&1)v[type^1].pb(i);
        else v[type].pb(i);

        if(cur>=2)v[type^1].pb(i+1);
        else v[type].pb(i+1);
    }

    //deve dar uns 80 pontos

    int target = (sz(v[0])>=k?0:1), ans = sz(v[0]);

    for(int i=2*k-1;i<n;i+=k){
        
        if(sz(v[target^1])>sz(v[target]))target ^= 1;
        k = sz(v[target]);

        vector<int>ask;
        for(int j=0;j<k&&i+j<n;++j){
            ask.pb(i+j), ask.pb(v[target][j]);
        }

        int cur = use_machine(ask);

        if(cur&1)v[target^1].pb(i);
        else v[target].pb(i);

        if(target==1)ans += (cur+1)/2;
        else ans += min(n-i,k) - (cur+1)/2;
    }

    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() {
// 	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;
// }

Compilation message (stderr)

mushrooms.cpp:82:1: warning: multi-line comment [-Wcomment]
   82 | // #define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
      | ^

• Subtask 1: 90.7631 / 100