Submission #545467

#	Time	Username	Problem	Language	Result	Execution time	Memory
545467		maomao90	Koala Game (APIO17_koala)	C++17	71 / 100	69 ms	440 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, 9), 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;
}

int res[105];
template <class T>
void my_sort(int *arr, int l, int r, T &&f) {
    int n = r - l;
    if (n <= 1) return;
    int m = l + r + 1 >> 1;
    my_sort(arr, l, m, f);
    my_sort(arr, m, r, f);
    int a = l, b = m, c = l;
    while (a < m && b < r) {
        if (f(arr[a], arr[b])) {
            res[c++] = arr[a++];
        } else {
            res[c++] = arr[b++];
        }
    }
    while (a < m) {
        res[c++] = arr[a++];
    }
    while (b < r) {
        res[c++] = arr[b++];
    }
    REP (i, l, r) {
        arr[i] = res[i];
    }
}

void allValues(int n, int w, int *p) {
    if (w == 2 * n) {
        int id[n];
        iota(id, id + n, 0);
        my_sort(id, 0, 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 {
        int id[n];
        iota(id, id + n, 0);
        my_sort(id, 0, n, [&] (int s, int e) {
                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[s] = b[e] = mid;
                    playRound(b, r);
                    bool is0 = r[s] > mid, is1 = r[e] > mid;
                    if (is0 != is1) {
                        if (is0) {
                            return 0;
                        } else {
                            return 1;
                        }
                    }
                    if (is0) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
                assert(0);
                return 0;
        });
        REP (i, 0, n) {
            p[id[i]] = i + 1;
        }
    }
}

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;
      |               ~~~^~~~
koala.cpp: In lambda function:
koala.cpp:162:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |                     mid = lo + hi >> 1;
      |                           ~~~^~~~
koala.cpp: In instantiation of 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>]':
koala.cpp:152:18:   required from here
koala.cpp:118:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
koala.cpp: In instantiation of 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>]':
koala.cpp:185:10:   required from here
koala.cpp:118:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
koala.cpp: In instantiation of 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>&]':
koala.cpp:119:12:   required from 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>]'
koala.cpp:152:18:   required from here
koala.cpp:118:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
koala.cpp: In instantiation of 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>&]':
koala.cpp:119:12:   required from 'void my_sort(int*, int, int, T&&) [with T = allValues(int, int, int*)::<lambda(int, int)>]'
koala.cpp:185:10:   required from here
koala.cpp:118:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]

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