제출 #895628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895628		Tenis0206	코알라 (APIO17_koala)	C++11	55 / 100	33 ms	600 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 find_value(int poz, int W)
{
    int st = 1;
    int dr = n;
    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;
            }
        }
        for(int i=0; i<mij; i++)
        {
            ++b[i];
        }
        playRound(b,r);
        if(r[poz] <= b[poz])
        {
            dr = mij - 1;
            rez = mij;
        }
        else
        {
            st = mij + 1;
        }
    }
    return rez;
}

/*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 greaterValue(int N, int W)
{
    return 0;
    //return comp(0,1,W);
}

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 val=1; val<=n; val++)
        {
            int poz = 0;
            for(int i=0; i<n; i++)
            {
                if(paux[i] == val)
                {
                    poz = i;
                    break;
                }
            }
            int st = 1;
            int dr = 200;
            int rez = 0;
            while(st<=dr)
            {
                int mij = (st + dr) >> 1;
                for(int i=0; i<n; i++)
                {
                    b[i] = r[i] = 1;
                }
                b[poz] = mij;
                playRound(b,r);
                if(r[poz] > b[poz])
                {
                    rez = mij;
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            cout<<rez<<'\n';
        }
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            sel[i] = false;
        }
        for(int val=n; val>=2; val--)
        {
            vector<int> c;
            for(int i=0; i<n; i++)
            {
                if(sel[i])
                {
                    continue;
                }
                c.push_back(i);
            }
            int poz = 0;
            int nr = 0;
            while(true)
            {
                ++nr;
                if(val > 54)
                {
                    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;
                if(c.size() == 1)
                {
                    poz = c.front();
                    break;
                }
            }
            P[poz] = val;
            sel[poz] = true;
        }
        for(int i=0; i<n; i++)
        {
            if(!sel[i])
            {
                P[i] = 1;
            }
        }
    }
}

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