Submission #421702

#	Time	Username	Problem	Language	Result	Execution time	Memory
421702		usachevd0	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2 ms	584 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) {
    if (n <= 2) {
        return 1 + (int)(use_machine({0, 1}) == 0);
    }
    
    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 minVal = 1e9;
    int minK = -1;
    for (int k = 1; k <= n; ++k) {
        if (2 * k >= n) break;
        if (chkmin(minVal, k + CeilD(n, k))) {
            minK = k;
        }
    }
    int k = minK;
    // debug(k);
    
    vector<int> col(n, -1);
    col[0] = 0;
    
    vector<int> h[2];
    h[0].push_back(0);
    for (int i = 1; i <= 2; ++i) {
        col[i] = ask({0, i});
        h[col[i]].push_back(i);
    }
    int i = 3;
    if (h[0].size() == 2) {
        while (true) {
            if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
            
            int res = ask({h[0][0], i, h[0][1], i + 1});
            if (res == 0) {
                col[i] = col[i + 1] = 0;
            } else if (res == 1) {
                col[i] = 0;
                col[i + 1] = 1;
            } else if (res == 2) {
                col[i] = 1;
                col[i + 1] = 0;
            } else {
                col[i] = col[i + 1] = 1;
            }
            h[col[i]].push_back(i);
            h[col[i + 1]].push_back(i + 1);
            i += 2;
        }
    } else {
        while (true) {
            if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
            
            int res = ask({h[1][0], i, h[1][1], i + 1});
            if (res == 3) {
                col[i] = col[i + 1] = 0;
            } else if (res == 2) {
                col[i] = 0;
                col[i + 1] = 1;
            } else if (res == 1) {
                col[i] = 1;
                col[i + 1] = 0;
            } else {
                col[i] = col[i + 1] = 1;
            }
            h[col[i]].push_back(i);
            h[col[i + 1]].push_back(i + 1);
            i += 2;
        }
    }
    
    int ans = h[0].size();
    if (h[0].size() >= k + 1) {
        for (; i < n; i += k) {
            int m = min(n, i + k) - i;
            vector<int> x = {h[0][0]};
            for (int j = 0; j < m; ++j) {
                x.push_back(i + j);
                x.push_back(h[0][j + 1]);
            }
            ans += m - ask(x) / 2;
        }
    } else {
        for (; i < n; i += k) {
            int m = min(n, i + k) - i;
            vector<int> x = {h[1][0]};
            for (int j = 0; j < m; ++j) {
                x.push_back(i + j);
                x.push_back(h[1][j + 1]);
            }
            ans += 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", answer);
    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:150:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                 ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:150:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                                         ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:170:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                 ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:170:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                                         ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:191:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  191 |     if (h[0].size() >= k + 1) {
      |         ~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 100