Submission #421508

#	Time	Username	Problem	Language	Result	Execution time	Memory
421508		usachevd0	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	231 ms	712 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_halfn(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;
}

int CeilD(int x, int y) {
    if (x % y)
        return x / y + 1;
    return x / y;
}

int count_mushrooms(int n) {
    vector<int> rem(n - 1);
    iota(all(rem), 1);
    
    const int maxS = 1e5;
    int maxQ = n;
    int asked = 0;
    int askedSum = 0;
    auto ask = [&](vector<int> x) {
        // debug(x);
        ++asked;
        askedSum += x.size();
        assert(asked <= maxQ);
        assert(askedSum <= maxS);
        return use_machine(x);
    };
    
    int ans = 1;
    int k = 0;
    vector<int> zeroes = {0};
    while (!rem.empty() && (!k || CeilD(rem.size(), k) > asked && askedSum + 2 * rem.size() + CeilD(rem.size(), k) < maxS / 2 && asked < maxQ / 2)) {
        if (ask({0, rem[0]}) == 0) {
            ++ans;
            ++k;
            zeroes.push_back(rem[0]);
            rem.erase(rem.begin());
            continue;
        }
        int vl = 0;
        int vr = rem.size();
        while (vr - vl > 1) {
            int vm = (vl + vr) >> 1;
            vector<int> x(rem.begin(), rem.begin() + vm + 1);
            x.insert(x.begin(), 0);
            if (ask(x) == 1)
                vl = vm;
            else
                vr = vm;
        }
        if (vl == rem.size() - 1) {
            rem.clear();
            break;
        }
        
        ++ans;
        ++k;
        zeroes.push_back(rem[vr]);
        vector<int> new_rem(rem.begin() + vr + 1, rem.end());
        swap(rem, new_rem);
    }
    
    while (!rem.empty()) {
        int m = min(k, (int)rem.size());
        vector<int> y;
        for (int i = 0; i < m; ++i) {
            y.push_back(rem.back());
            rem.pop_back();
        }
        vector<int> x = {0};
        for (int i = 0; i < m; ++i) {
            x.push_back(y[i]);
            x.push_back(zeroes[i + 1]);
        }
        ans += m - ask(x) / 2;
    }
    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

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:129:127: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  129 |     while (!rem.empty() && (!k || CeilD(rem.size(), k) > asked && askedSum + 2 * rem.size() + CeilD(rem.size(), k) < maxS / 2 && asked < maxQ / 2)) {
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
mushrooms.cpp:148:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         if (vl == rem.size() - 1) {
      |             ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100