Submission #895664

#	Time	Username	Problem	Language	Result	Execution time	Memory
895664		Tenis0206	Koala Game (APIO17_koala)	C++11	74 / 100	26 ms	700 KiB

koala

#include <bits/stdc++.h>
#include "koala.h"

using namespace std;

const int nmax = 100;

int n;

int b[nmax + 5], r[nmax + 5];

int paux[nmax + 5];

bool sel[nmax + 5];

int p[nmax + 5];

map<pair<int,int>,int> mp;

vector<int> lc[nmax + 5];

/*int comp(int pa, int pb)
{
    int st = 1;
    int dr = n - 2;
    int rez = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        for(int i=0;i<n;i++)
        {
            r[i] = 0, b[i] = 0;
        }
        if(W == 200)
        {
            for(int i=0;i<n;i++)
            {
                b[i] = 1;
            }
        }
        int nr = 0;
        for(int i=0;i<n && nr < mij;i++)
        {
            if(i == pa || i == pb)
            {
                continue;
            }
            ++b[i];
            ++nr;
        }
        playRound(b,r);
        if(r[pa] <= b[pa] && r[pb] > b[pb])
        {
            return pb;
        }
        if(r[pb] <= )
        if(r[poz] <= b[poz])
        {
            dr = mij - 1;
            rez = mij;
        }
        else
        {
            st = mij + 1;
        }
    }
    return rez;
}
*/

int minValue(int N, int W)
{
    n = N;
    for(int i=0; i<n; i++)
    {
        b[i] = 0;
        r[i] = 0;
    }
    b[0] = 1;
    playRound(b,r);
    for(int i=0; i<n; i++)
    {
        if(r[i] <= b[i])
        {
            return i;
        }
    }
    return 0;
}

int maxValue(int N, int W)
{
    n = N;
    vector<int> c;
    for(int i=0; i<n; i++)
    {
        c.push_back(i);
    }
    int nr = 0;
    while(true)
    {
        ++nr;
        while((nr + 1) * (int)(c.size()) <= W)
        {
            ++nr;
        }
        for(int i=0; i<n; i++)
        {
            b[i] = 0, r[i] = 0;
        }
        for(auto it : c)
        {
            b[it] = nr;
        }
        playRound(b,r);
        vector<int> aux;
        for(auto it : c)
        {
            if(r[it] > b[it])
            {
                aux.push_back(it);
            }
        }
        c = aux;
        if(c.size() == 1)
        {
            return c.front();
        }
    }
    return 0;
}

int cmp(int x, int y)
{
    if(x == -1)
    {
        return y;
    }
    if(y == -1)
    {
        return x;
    }
    for(int i=0; i<n; i++)
    {
        b[i] = r[i] = 0;
    }
    b[x] = 100;
    b[y] = 100;
    playRound(b,r);
    if(r[x] == 101)
    {
        return y;
    }
    return x;
}

int ai[4 * nmax + 5];

void preset(int nod, int st, int dr)
{
    if(st == dr)
    {
        ai[nod] = st - 1;
        return;
    }
    int mij = (st + dr) >> 1;
    preset(nod*2,st,mij);
    preset(nod*2+1,mij+1,dr);
    ai[nod] = cmp(ai[nod*2],ai[nod*2+1]);
}

void update(int poz, int val, int nod, int st, int dr)
{
    if(st==dr)
    {
        ai[nod] = val;
        return;
    }
    int mij = (st + dr) >> 1;
    if(poz <= mij)
    {
        update(poz,val,nod*2,st,mij);
    }
    else
    {
        update(poz,val,nod*2+1,mij+1,dr);
    }
    ai[nod] = cmp(ai[nod*2],ai[nod*2+1]);
}

int greaterValue(int N, int W)
{
    return 0;
}

void allValues(int N, int W, int *P)
{
    n = N;

#ifdef home
    ifstream f("nr.in");
    int a,bb,c,d;
    f>>a>>bb>>c>>d;
    for(int i=0; i<n; i++)
    {
        f>>paux[i];
    }
#endif // home
    if (W == 2*N)
    {
        for(int i=0; i<n; i++)
        {
            p[i] = i;
        }
        preset(1,1,n);
        for(int i=0; i<n; i++)
        {
            p[i] = ai[1];
            update(p[i] + 1, -1,1,1,n);
        }
        for(int i=0; i<n; i++)
        {
            P[p[i]] = i + 1;
        }
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            sel[i] = false;
        }
        vector<int> c;
        for(int i=0; i<n; i++)
        {
            if(sel[i])
            {
                continue;
            }
            c.push_back(i);
        }
        lc[n] = c;
        for(int val=n; val>=1; val--)
        {
            c.clear();
            for(int len=n-val+1; len<=n; len++)
            {
                if(!lc[len].empty())
                {
                    for(auto it : lc[len])
                    {
                        if(sel[it])
                        {
                            continue;
                        }
                        c.push_back(it);
                    }
                    break;
                }
            }
            if(c.size() != 1)
            {
                int nr = 0;
                int poz = 0;
                while(true)
                {
                    ++nr;
                    if(val > 96)
                    {
                        while((nr + 1) * (int)(c.size()) + (n - val) <= W)
                        {
                            ++nr;
                        }
                    }
                    for(int i=0; i<n; i++)
                    {
                        b[i] = 0, r[i] = 0;
                    }
                    for(auto it : c)
                    {
                        b[it] = nr;
                    }
                    playRound(b,r);
                    vector<int> aux;
                    for(auto it : c)
                    {
                        if(r[it] > b[it])
                        {
                            aux.push_back(it);
                        }
                    }
                    c = aux;
                    int len = c.size() + n - val;
                    lc[len] = c;
                    if(c.size() == 1)
                    {
                        poz = c.front();
                        break;
                    }
                }
                P[poz] = val;
                sel[poz] = true;
            }
            else
            {
                int poz = c.front();
                P[poz] = val;
                sel[poz] = true;
            }
        }
    }
}

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