제출 #1310316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310316		Faisal_Saqib	코알라 (APIO17_koala)	C++20	68 / 100	66 ms	512 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.
    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;
}

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.
    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);
        }
    }
    // cout<<"At "<<l<<' '<<r<<endl;
    // cout<<"High: ";
    // for(auto x:high)cout<<x<<' ';
    // cout<<endl;
    // cout<<"low: ";
    // for(auto x:low)cout<<x<<' ';
    // cout<<endl;
    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;
    if (w == n) {
        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];
        }
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

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