Submission #1260153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260153		hamanp87	Koala Game (APIO17_koala)	C++20	82 / 100	18 ms	440 KiB

koala

#include "koala.h" 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int inf=1e9,mod=1e9+7,neginf=-1e9,N=100;
const double PI=acos(-1);
int gn,gw;
int tos[N],res[N],ss[N];

inline void ZS(int n)
{
    fill(tos,tos+n,0);
}

int minValue(int n,int w)
{
    gn=n;
    gw=w;
    ZS(n);
    tos[0]=1;
    playRound(tos,res);
    for(int i=0;i<n;i++)
        if(res[i]==0)
            return i;

    return 0;
}

int maxValue(int n,int w)
{
    gn=n;
    gw=w;

    veci cans;
    cans.reserve(n);
    for(int i=0;i<n;i++)
        cans.pub(i);

    while(cans.size()>1)
    {
        int cnt=w/(int)cans.size();
        if(cnt<=0)
            cnt=1;

        ZS(n);
        for(int ind:cans)
            tos[ind]=cnt;
        playRound(tos,res);

        veci nxt;
        nxt.reserve(cans.size());
        for(int ind:cans)
            if(res[ind]>cnt)
                nxt.pub(ind);
        if(nxt.empty())
        {
            int bst=-1;
            for(int ind:cans)
                bst=max(bst,res[ind]);
            for(int ind:cans)
                if(res[ind]==bst)
                    nxt.pub(ind);
        }
        swap(cans,nxt);
    }

    return cans.empty()?0:cans[0];
}

int greaterValue(int n,int w)
{
    gn=n;
    gw=w;

    int L=0,R=w;
    while(L+1<R)
    {
        int mid=(L+R)>>1;
        int sn=min(mid,w/2);
        ZS(n);
        tos[0]=tos[1]=sn;
        playRound(tos,res);

        bool al=(res[0]<=sn);
        bool bl=(res[1]<=sn);

        if(al and bl)
            R=mid;
        else if(!al and !bl)
            L=mid;
        else
            return (res[0]<res[1])?0:1;
    }

    int sn=min(R,w/2);
    ZS(n);
    tos[0]=sn;
    tos[1]=sn;
    playRound(tos,res);

    return (res[0]<res[1])?0:1;
}

bool cmp1(int a,int b)
{
    int pr=max(1,gw/2);
    ZS(gn);
    tos[a]=tos[b]=pr;
    playRound(tos,res);

    return res[a]<res[b];
}

void C1(int ll,int lr,int rl,int rr)
{
    queue<int> a,b,c;
    for(int i=ll;i<=lr;i++)
        a.push(ss[i]);
    for(int i=rl;i<=rr;i++)
        b.push(ss[i]);

    while(a.size() and b.size())
    {
        if(cmp1(a.front(),b.front()))
        {
            c.push(a.front());
            a.pop();
        }
        else
        {
            c.push(b.front());
            b.pop();
        }
    }

    while(a.size())
    {
        c.push(a.front());
        a.pop();
    }
    while(b.size())
    {
        c.push(b.front());
        b.pop();
    }

    for(int i=ll;i<=rr;i++)
    {
        ss[i]=c.front();
        c.pop();
    }
}

void D1(int l,int r)
{
    if(l>=r)
        return;
    int mid=(l+r)>>1;
    D1(l,mid+0);
    D1(mid+1,r);
    C1(l,mid,mid+1,r);
}

inline int tri(int k)
{
    return (k*(k+1)/2)+k*k;
}

int BS(int v)
{
    int L=-1,R=17;
    while(L+1<R)
    {
        int mid=(L+R)>>1;
        if(tri(mid)<v)
            L=mid;
        else
            R=mid;
    }

    return R;
}

void SR(int l,int r,const veci &inds)
{
    if(inds.empty())
        return;
    if(l==r)
    {
        for(int id:inds)
            ss[id]=l;
        return;
    }

    int len=r-l+1;
    int m=min(max(1,gw/max(1,(int)inds.size())),BS(r));

    ZS(gn);
    for(int id:inds)
        tos[id]=m;
    playRound(tos,res);

    veci la,ra;
    int lr=l-1;
    for(int id:inds)
    {
        if(res[id]<=m)
        {
            la.pub(id);
            lr++;
        }
        else
        {
            ra.pub(id);
        }
    }

    if(la.size())
        SR(l,lr,la);
    if(ra.size())
        SR(lr+1,r,ra);
}

void allValues(int n,int w,int *p)
{
    gn=n;
    gw=w;

    if(w==2*n)
    {
        for(int i=0;i<n;i++)
            ss[i]=i;
        D1(0,n-1);
        for(int i=0;i<n;i++)
            p[ss[i]]=i+1;
    }
    else
    {
        veci inds;
        inds.reserve(n);
        for(int i=0;i<n;i++)
            inds.pub(i);

        SR(1,100,inds);

        for(int i=0;i<n;i++)
            p[i]=ss[i];
    }
}

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