Submission #421488

#	Time	Username	Problem	Language	Result	Execution time	Memory
421488		usachevd0	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	147 ms	292 KiB

mushrooms

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "mushrooms.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& e : v)
        stream << e << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


int use_machine(vector<int> x);
int count_mushrooms(int n) {
    if (n == 2) {
        if (use_machine({0, 1}) == 1)
            return 1;
        return 2;
    }
    
    int ans = 1;
    int x, y;
    int i;
    if (use_machine({0, 1}) == 0) {
        x = 0;
        y = 1;
        i = 2;
        ++ans;
    } else if (use_machine({0, 2}) == 0) {
        x = 0;
        y = 2;
        i = 3;
        ++ans;
    } else {
        x = 1;
        y = 2;
        i = 3;
    }
    for (; i < n; i += 2) {
        if (i == n - 1) {
            ans += use_machine({0, i}) == 0;
            break;
        }
        int res = use_machine({x, i, y, i + 1});
        if (x == 0) {
            if (res == 0)
                ans += 2;
            else if (res <= 2)
                ++ans;
        } else {
            if (res == 3)
                ans += 2;
            else if (res >= 1)
                ++ans;
        }
    }
    return ans;
}



#ifdef LOCAL


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() {
    freopen("in", "r", stdin);
    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;
}


// int32_t main() {
//     #ifdef LOCAL
//         freopen("in", "r", stdin);
//     #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    
    
    
//     return 0;
// }


#endif

• Subtask 1: 25 / 100