Submission #261469

#	Time	Username	Problem	Language	Result	Execution time	Memory
261469		Kastanda	Koala Game (APIO17_koala)	C++11	100 / 100	79 ms	632 KiB

koala

// M
#include<bits/stdc++.h>
#include "koala.h"
using namespace std;
const int N = 109;
int B[N], R[N];

int minValue(int n, int W)
{
        for (int i = 0; i < n; i ++)
                B[i] = 1;
        playRound(B, R);
        int id = -1;
        for (int i = 0; i < n; i ++)
                if (R[i] > 1)
                        id = i;
        assert(id != -1);
        memset(B, 0, sizeof(B));
        B[id] = 1;
        playRound(B, R);
        for (int i = 0; i < n; i ++)
                if (!R[i])
                        return i;
}

int maxValue(int n, int W)
{
        vector < int > Cnds;
        for (int i = 0; i < n; i ++)
                Cnds.push_back(i);
        while (Cnds.size() > 1)
        {
                memset(B, 0, sizeof(B));
                for (int a : Cnds)
                        B[a] = W / (int)Cnds.size();
                playRound(B, R);
                vector < int > TbC;
                for (int a : Cnds)
                        if (R[a] > B[a])
                                TbC.push_back(a);
                Cnds.swap(TbC);
                TbC.clear();
        }
        assert(Cnds.size());
        return Cnds[0];
}

int greaterValue(int n, int W)
{
        int le = 0, ri = min(11, W / 2), md;
        while (ri - le > 1)
        {
                md = (le + ri) >> 1;
                memset(B, 0, sizeof(B));
                B[0] = md; B[1] = md;
                playRound(B, R);
                int w0 = R[0] > md, w1 = R[1] > md;
                if (w0 && !w1)
                        return 0;
                if (w1 && !w0)
                        return 1;
                if (w0 && w1)
                        le = md;
                else
                        ri = md;
        }
}

inline bool TestRound(int l, int r, int n, int W, int Cw)
{
        if (Cw * (r - l + 1) > W)
                return 0;
        memset(B, 0, sizeof(B));
        for (int i = 0; i < n; i ++)
                B[i] = 0;
        for (int i = l; i <= r; i ++)
                B[i - 1] = Cw;

        int ORGP[210];
        for (int i = 0; i < n; i ++)
                ORGP[i] = i + 1;

    int i, j;

    int cache[2][205];
    int num[2][205];
    char taken[105][205];

    for (i=0;i<205;++i) {
        cache[1][i] = 0;
        num[1][i] = 0;
    }

    for (i=0;i<n;++i) {
        int v = B[i]+1;
        int ii = i&1;
        int o = ii^1;
        for (j=0;j<=W;++j) {
            cache[ii][j] = cache[o][j];
            num[ii][j] = num[o][j];
            taken[i][j] = 0;
        }
        for (j=W;j>=v;--j) {
            int h = cache[o][j-v] + ORGP[i];
            int hn = num[o][j-v] + 1;
            if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
                cache[ii][j] = h;
                num[ii][j] = hn;
                taken[i][j] = 1;
            } else {
                taken[i][j] = 0;
            }
        }
    }

    int cur = W;
    for (i=n-1;i>=0;--i) {
        R[i] = taken[i][cur] ? (B[i] + 1) : 0;
        cur -= R[i];
    }

        int Pkd = 0;
        for (int i = l; i <= r; i ++)
                if (R[i - 1] > B[i - 1])
                        Pkd ++;
        if (Pkd == 0 || Pkd == r - l + 1)
                return 0;
        return 1;
}

void Solve(int l, int r, vector < int > A, int n, int W, int * P)
{
        if (r < l)
                return ;
        if (l == r)
                return void(P[A[0]] = l);


        int w = W / n;
        int Cw = W;
        /*for (int i = r + 1; i <= n; i ++)
                B[i] = w - 1, Cw -= B[i];*/
        Cw /= (r - l + 1);
        while (Cw && !TestRound(l, r, n, W, Cw))
                Cw --;
        assert(Cw);

        memset(B, 0, sizeof(B));
        for (int i : A)
                B[i] = Cw;

        playRound(B, R);
        vector < int > Le, Ri;
        for (int i : A)
        {
                if (R[i] > B[i])
                        Ri.push_back(i);
                else
                        Le.push_back(i);
        }

        /*printf("Left, from %d to %d is : ", l, l + (int)Le.size() - 1);
        for (int a : Le) printf("%d ", a); printf("\n");

        printf("Right, from %d to %d is : ", l + (int)Le.size(), r);
        for (int a : Ri) printf("%d ", a); printf("\n");*/

        Solve(l, l + (int)Le.size() - 1, Le, n, W, P);
        Solve(l + (int)Le.size(), r, Ri, n, W, P);
        return ;
}

void allValues(int n, int W, int * P)
{
        vector < int > A;
        for (int i = 0; i < n; i ++)
                A.push_back(i);
        Solve(1, n, A, n, W, P);
}

Compilation message (stderr)

koala.cpp: In function 'void Solve(int, int, std::vector<int>, int, int, int*)':
koala.cpp:139:13: warning: unused variable 'w' [-Wunused-variable]
         int w = W / n;
             ^
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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