제출 #1310319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310319		Faisal_Saqib	코알라 (APIO17_koala)	C++20	87 / 100	612 ms	1276 KiB

koala

#include "koala.h"
#include <vector>
#include <set>
#include <iostream>
#include <map>
using namespace std;

int minValue(int n, int w) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int* b=new int[n];
    int* r=new int[n];
    b[0]=1;
    playRound(b,r);
    for(int i=0;i<n;i++)
    {
        if(r[i]==0)
            return i;
    }
    return 0;
}

int maxValue(int n, int w) {
    int* b=new int[n];
    int* r=new int[n];
    for(int i=0;i<n;i++)b[i]=1;
    playRound(b,r);
    set<int> pos;
    for(int i=0;i<n;i++)
    {
        if(r[i]>0)
        {
            pos.insert(i);
            // cout<<i<<' ';
        }
    }
    // cout<<endl;
    for(int i=0;i<n;i++)
    {
        b[i]=0;
    }
    for(auto x:pos)
    {
        b[x]=2;
    }
    playRound(b,r);
    pos.clear();
    for(int i=0;i<n;i++)
    {
        if(r[i]>0 and b[i]==2)
        {
            pos.insert(i);
            // cout<<i<<' ';
        }
    }
    // cout<<endl;
    

    for(int i=0;i<n;i++)
    {
        b[i]=0;
    }
    for(auto x:pos)
    {
        b[x]=4;
    }
    playRound(b,r);
    pos.clear();
    for(int i=0;i<n;i++)
    {
        if(r[i]>0 and b[i]==4)
        {
            pos.insert(i);
            // cout<<i<<' ';
        }
    }
    // cout<<endl;

    for(int i=0;i<n;i++)
    {
        b[i]=0;
    }
    for(auto x:pos)
    {
        b[x]=11;
    }
    playRound(b,r);
    pos.clear();
    for(int i=0;i<n;i++)
    {
        if(r[i]>0 and b[i]==11)
        {
            return i;
            // pos.insert(i);
            // cout<<i<<' ';
        }
    }
    // cout<<endl;
    return 0;
}


const int MPL=500;
int fnl[MPL],n,w;
int* b;
int* rt;
void Simulate(int *B, int *R) {
    int i, j;
    int S = 0;
    for (i=0;i<n;++i) {
        S += B[i];
    }
    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] + i+1;
            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];
    }
}
void recur(int l,int r,set<int>&ind)
{
    if(l==r)
    {
        fnl[*begin(ind)]=l;
        return;
    }
    for(int i=0;i<n;i++)b[i]=0;
    int bst=1,dif=ind.size();
    for(int pl=1;pl<=(w/(int)ind.size());pl++)
    {
        for(int x=l;x<=r;x++)
        {
            b[x-1]=pl;
        }
        Simulate(b,rt);
        set<int> high,low;
        for(int x=l-1;x<=r-1;x++)
        {
            if(rt[x]>b[x])
            {
                high.insert(x);
            }
            else
            {
                low.insert(x);
            }
        }
        int cdif=abs((int)low.size() - (int)high.size());
        if(cdif<dif)
        {
            dif=cdif;
            bst=pl;
        }
    }
    for(int i=0;i<n;i++)b[i]=0;
    for(auto x:ind)
    {
        b[x]=bst;
    }
    playRound(b,rt);
    set<int> high,low;
    for(auto x:ind)
    {
        if(rt[x]>b[x])
        {
            high.insert(x);
        }
        else
        {
            low.insert(x);
        }
    }
    if(low.size()==0 or high.size()==0)return;
    recur(l,r-(int)high.size(),low);
    recur(l+(int)low.size(),r,high);
}
void allValues(int N, int W, int *P) {
    ::n=N;
    ::w=W;
    b=new int[n];
    rt=new int[n];
    set<int> cur;
    for(int i=0;i<n;i++)cur.insert(i);
    recur(1,n,cur);
    for(int i=0;i<n;i++)
    {
        P[i]=fnl[i];
    }
}



int recur_spe(int l,int r,set<int>&ind)
{
    if(l==r)
    {
        fnl[*begin(ind)]=l;
        return -1;
    }
    for(int i=0;i<n;i++)b[i]=0;
    int bst=1,dif=-1,len=(r-l+1);
    for(int pl=1;pl<=(w/(int)ind.size());pl++)
    {
        for(int x=l;x<=r;x++)
        {
            b[x-1]=pl;
        }
        Simulate(b,rt);
        set<int> high,low;
        for(int x=l-1;x<=r-1;x++)
        {
            if(rt[x]>b[x])
            {
                high.insert(x);
            }
            else
            {
                low.insert(x);
            }
        }
        int cdif=abs((int)low.size() - (int)high.size());
        if(low.size()>0 and high.size()>0 and cdif<=(len/3) and cdif>=dif)
        {
            dif=cdif;
            bst=pl;
        }
    }
    for(int i=0;i<n;i++)b[i]=0;
    for(auto x:ind)
    {
        b[x]=bst;
    }
    playRound(b,rt);
    set<int> high,low;
    for(auto x:ind)
    {
        if(rt[x]>b[x])
        {
            high.insert(x);
        }
        else
        {
            low.insert(x);
        }
    }
    if((low.find(0)!=low.end() and low.find(1)!=low.end()))
    {
        // both in the same bucket
        return recur_spe(l,r-(int)high.size(),low);
    }
    else if((high.find(0)!=high.end() and high.find(1)!=high.end()))
    {
        return recur_spe(l+(int)low.size(),r,high);
    }
    else
    {
        // both in different buckets
        return (high.find(0)==high.end());
    }
}
int greaterValue(int n, int w) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    ::n=n;
    ::w=w;
    b=new int[n];
    rt=new int[n];
    set<int> cur;
    for(int i=0;i<n;i++)cur.insert(i);
    return recur_spe(1,n,cur);
    // return ;
}

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