Submission #1286722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286722		edo	Counting Mushrooms (IOI20_mushrooms)	C++20	100 / 100	6 ms	1352 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

#include "mushrooms.h"

vi correct;
int used = 0;

// int use_machine(vi a) {
//     used++;
//     int n = sz(a);
//     int ans = 0;
//     FOR(n - 1) {
//         if(correct[a[i]] != correct[a[i + 1]]) ans++;
//     }
//     return ans;
// }

// int lim = 125; // mozda se mora smanjiti
// int lim = 95;
int lim = 105;

int count_mushrooms(int n) {
    int ans = 1;
    set<int> nepoz;
    FOR(i, 1, n) 
        nepoz.emplace(i);

    vi a = {0}, b;

    while(!nepoz.empty() && max(sz(a), sz(b)) < lim) {
        if(sz(nepoz) == 1 || max(sz(a), sz(b)) == 1) {
            int u = *nepoz.begin();
            nepoz.erase(u);
            int q = use_machine({0, u});
            if(q) 
                b.pb(u);
            else {
                a.pb(u);
                ans++;
            }
        }
        else if(sz(nepoz) < 5 || max(sz(a), sz(b)) < 3 || min(sz(a), sz(b)) < 2) {
            int u = *nepoz.begin(); nepoz.erase(u); 
            int v = *nepoz.begin(); nepoz.erase(v); 

            bool o = sz(a) < 2; // moze se desiti
            int old = sz(a);
            if(o) swap(a, b);
            int q = use_machine({a[0], u, a[1], v});
            if(!q) {
                a.pb(u);
                a.pb(v);
            }
            else if(q == 1) {
                b.pb(v);
                a.pb(u);
            }
            else if(q == 2) {
                b.pb(u);    
                a.pb(v);
            }
            else {
                b.pb(u);
                b.pb(v);
            }
            if(o)
                swap(a, b);
            ans += sz(a) - old;
        }
        else {
            int old = sz(a);
            bool o = sz(a) < sz(b);
            if(o) swap(a, b);

            int u = *nepoz.begin(); nepoz.erase(u);
            int v = *nepoz.begin(); nepoz.erase(v);
            int w = *nepoz.begin(); nepoz.erase(w);
            int q = use_machine({a[0], u, a[1], v, a[2], w});
            if(q & 1) {
                b.pb(w);
                q--;
            }
            else {
                a.pb(w);
            }
            if(!q) {
                a.pb(u);
                a.pb(v);
            }
            else if(q == 4) {
                b.pb(u);
                b.pb(v);
            }
            else {
                int c = *nepoz.begin(); nepoz.erase(c);
                int d = *nepoz.begin(); nepoz.erase(d); 

                q = use_machine({b[0], u, b[1], a[0], v, a[1], c, a[2], d}) - 1;
                // max q = 7
                if(q & 1) {
                    b.pb(d);
                }
                else {
                    a.pb(d);
                }
                if(q & 2) {
                    // odlucuje c za {q = 6 & q = 2 (q - 1)}
                    b.pb(c);
                }
                else {
                    a.pb(c);
                }
                if(q & 4) {
                    // odlucuje u i v {q = 4 & q = 6 (q - 1)};
                    b.pb(v);
                    a.pb(u);
                }
                else {
                    a.pb(v);
                    b.pb(u);
                }
            }
            if(o) swap(a, b);
            ans += sz(a) - old;
        }
    }


    while(!nepoz.empty()) {
        vi Q;
        bool o = sz(a) < sz(b);
        if(o) swap(a, b);
        trav(x, a) {
            Q.pb(x);
            Q.pb(*nepoz.begin());
            nepoz.erase(nepoz.begin());
            if(nepoz.empty()) break;
        }
        int q = use_machine(Q);
        if(q & 1) {
            b.pb(Q.back());
        } 
        else {
            a.pb(Q.back());
        }
        if(o) swap(a, b);
        ans += o ? ((q + 1) / 2) : ((sz(Q) / 2) - (q + 1) / 2);
    }
    return ans;
}

// int32_t main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int n;
//     sc(n);
//     correct.resize(n);
//     sc(correct);
//     int ans = count_mushrooms(n);
//     // pt(ans); nl;
//     // pt(count(all(correct), 0)); nl;
//     pt(ans, "\nUsed:", used); nl;
//     return 0;
// }

• Subtask 1: 100 / 100