Submission #1030345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030345		vjudge1	Koala Game (APIO17_koala)	C++17	90 / 100	52 ms	1868 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(243987);
int you[100],cnt;
int minValue(int N, int W) {
    int me[100]{1};
    playRound(me,you),cnt++;
    for(int i=0;i<N;i++)
        if(you[i]==0)
            return i;
    return 0;
}

int maxValue(int N, int W) {
    int me[100];
    vector<int>theposs(N);
    iota(theposs.begin(),theposs.end(),0);
    while(theposs.size()>1){
        memset(me,0,sizeof me);
        for(auto i:theposs)
            me[i]=W/theposs.size();
        playRound(me,you),cnt++;
        vector<int>theposs2;
        for(auto i:theposs)
            if(you[i])theposs2.push_back(i);
        theposs=theposs2;
    }
    return theposs[0];
}
int greaterValue(int N, int W) {
    int me[100]{1,1};
    int L=1,R=8;
    while(L<=R){
        int mid=L+R>>1;
        me[0]=mid;
        me[1]=mid;
        playRound(me,you),cnt++;
        if(you[0]-you[1])
            return cerr<<mid,!you[0];
        if(you[0])
            L=mid+1+(L==1&&R==8);
        else R=mid-1;
        L=min(R,L);
    }
    return 0;
}
int lst[101];
int smal[101];
int greaterValue2(int A, int B){
    int me[100];
    int L=1,R=8;
    while(L<=R){
        int mid=L+R>>1;
        me[A]=mid;
        me[B]=mid;
        playRound(me,you),cnt++;
        if(you[A]-you[B])
            return cerr<<mid,!you[A];
        if(you[A])
            L=mid+1+(L==1&&R==8);
        else R=mid-1;
        L=min(R,L);
    }
    return 0;
}
vector<int>result;
void playmyround(int *B, int *R) {
    int i, j;

    int S = 0;
    for (i=0;i<100;++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<100;++i) {
        int v = B[i]+1;
        int ii = i&1;
        int o = ii^1;
        for (j=0;j<=100;++j) {
            cache[ii][j] = cache[o][j];
            num[ii][j] = num[o][j];
            taken[i][j] = 0;
        }
        for (j=100;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 = 100;
    for (i=100-1;i>=0;--i) {
        R[i] = taken[i][cur] ? (B[i] + 1) : 0;
        cur -= R[i];
    }
}
void divide(vector<int>v,int l,int r){
    if(l>r) return;
    if(l==r) return result.push_back(v[0]);
    vector<int>v1,v2;
    int me[100]{},you[100],you2[100];
    for(int i=1;i<=8;i++){
        for(int j=l-1;j<r;j++)
            me[j]++;
        playmyround(me,you);
        int yes=0,no=0;
        for(int j=l-1;j<r;j++)
            if(you[j]==i+1)
                yes=1;
            else no=1;
        if(yes&&no){
            for(int j=l-1;j<r;j++)
                me[j]=0;
            for(auto x:v)
                me[x]=i;
            playRound(me,you2);
            for(auto x:v)
                if(you2[x]==i+1)
                    v1.push_back(x);
                else v2.push_back(x);
            break;
        }
    }
    divide(v1,r-v1.size()+1,r);
    divide(v2,l,l+v2.size()-1);
}
void allValues(int N, int W, int *P) {  
    vector<int>v(N);
    iota(v.begin(),v.end(),0);

    divide(v,1,N);
    for(int i=0;i<N;i++)
        P[result[i]]=N-i;
}

Compilation message (stderr)

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid=L+R>>1;
      |                 ~^~
koala.cpp: In function 'int greaterValue2(int, int)':
koala.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid=L+R>>1;
      |                 ~^~

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