Submission #545438

#	Time	Username	Problem	Language	Result	Execution time	Memory
545438		maomao90	Koala Game (APIO17_koala)	C++17	33 / 100	71 ms	336 KiB

koala

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "koala.h"
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int minValue(int n, int w) {
    int b[n], r[n];
    REP (i, 0, n) {
        b[i] = 0;
    }
    b[0] = 1;
    playRound(b, r);
    REP (i, 0, n) {
        if (r[i] == 0) {
            return i;
        }
    }
    assert(0);
}

int maxValue(int n, int w) {
    int b[n], r[n];
    REP (i, 0, n) {
        b[i] = 1;
    }
    playRound(b, r);
    vi big;
    REP (i, 0, n) {
        if (r[i] > 1) {
            big.pb(i);
        }
    }
    while (big.size() > 1) {
        int x = w / big.size();
        REP (i, 0, n) {
            b[i] = 0;
        }
        for (int i : big) {
            b[i] = x;
        }
        playRound(b, r);
        big.clear();
        REP (i, 0, n) {
            if (r[i] > 1) {
                big.pb(i);
            }
        }
    }
    assert(big.size() == 1);
    return big[0];
}

int greaterValue(int n, int w) {
    int lo = 1, hi = min(w / 2, 8), mid;
    while (lo <= hi) {
        mid = lo + hi >> 1;
        int b[n], r[n];
        REP (i, 0, n) {
            b[i] = 0;
        }
        b[0] = b[1] = mid;
        playRound(b, r);
        bool is0 = r[0] > mid, is1 = r[1] > mid;
        if (is0 != is1) {
            if (is0) {
                return 0;
            } else {
                return 1;
            }
        }
        if (is0) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    assert(0);
    return 0;
}

void allValues(int n, int w, int *p) {
    if (w == 2 * n) {
        int id[n];
        iota(id, id + n, 0);
        sort(id, id + n, [&] (int l, int r) {
                int b[n], c[n];
                REP (i, 0, n) {
                    b[i] = 0;
                }
                b[l] = b[r] = n;
                playRound(b, c);
                return c[l] <= n;
                });
        REP (i, 0, n) {
            p[id[i]] = i + 1;
        }
    } else {
    }
}

Compilation message (stderr)

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         mid = lo + hi >> 1;
      |               ~~~^~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 14 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 53