Submission #810470

#	Time	Username	Problem	Language	Result	Execution time	Memory
810470		oscar1f	Koala Game (APIO17_koala)	C++17	75 / 100	38 ms	580 KiB

koala

#include<bits/stdc++.h>
#include "koala.h"

using namespace std;

int coeff;
int posVal[100];
vector<int> init(100);

vector<int> jouer(vector<int> a) {
    /*for (int i:a) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    vector<int> b(100);
    playRound(a.data(),b.data());
    return b;
}

int minValue(int N, int W) {
    vector<int> rep(N),quest(N);
    quest[0]=1;
    rep=jouer(quest);
    for (int i=1;i<N;i++) {
        if (rep[i]==0) {
            return i;
        }
    }
    return 0;
}

int maxValue(int N, int W) {
    vector<int> rep(N),quest(N);
    vector<int> listeGrand,nouv;
    int nbMis;
    for (int i=0;i<N;i++) {
        quest[i]=1;
        listeGrand.push_back(i);
    }
    vector<int> tailleTour={1,2,4,11};
    reverse(tailleTour.begin(),tailleTour.end());
    while (listeGrand.size()>1) {
        /*cout<<listeGrand.size()<<" : ";
        for (int i:listeGrand) {
            cout<<i<<" ";
        }
        cout<<endl;*/
        nbMis=tailleTour.back();
        tailleTour.pop_back();
        nouv.clear();
        quest=init;
        for (int i:listeGrand) {
            quest[i]=nbMis;
        }
        rep=jouer(quest);
        for (int i:listeGrand) {
            if (rep[i]>nbMis) {
                nouv.push_back(i);
            }
        }
        listeGrand=nouv;
    }
    return listeGrand.back();
}

int greaterValue(int N, int W) {
    vector<int> rep(N),quest(N);
    int deb=1,fin=13,mid;
    while (1>0) {
        mid=(deb+fin)/2;
        quest[0]=mid;
        quest[1]=mid;
        rep=jouer(quest);
        if (rep[0]>mid and rep[1]<=mid) {
            return 0;
        }
        if (rep[1]>mid and rep[0]<=mid) {
            return 1;
        }
        if (rep[0]>mid) {
            deb=mid+1;
        }
        else {
            fin=mid-1;
        }
    }
    return 42;
}

void solve(int deb,int fin,vector<int> pos) {
    /*cout<<deb<<" "<<fin<<" : ";
    for (int i:pos) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    if (deb>fin) {
        return ;
    }
    if (deb==fin) {
        posVal[pos[0]]=deb;
        return;
    }
    vector<int> petit,grand,quest,rep;
    for (int i=coeff;i<=13*coeff;i+=coeff) {
        petit.clear();
        grand.clear();
        quest=init;
        for (int j:pos) {
            quest[j]=i;
        }
        rep=jouer(quest);
        for (int j:pos) {
            if (rep[j]>i) {
                grand.push_back(j);
            }
            else {
                petit.push_back(j);
            }
        }
        //cout<<petit.size()<<" "<<grand.size()<<endl;
        if (!grand.empty() and !petit.empty()) {
            solve(deb,deb+petit.size()-1,petit);
            solve(deb+petit.size(),fin,grand);
            return;
        }
    }
}

void allValues(int N, int W, int *P) {
    vector<int> deb;
    if (W==100) {
        coeff=1;
    }
    else {
        coeff=2;
    }
    for (int i=0;i<N;i++) {
        deb.push_back(i);
    }
    solve(1,N,deb);
    /*for (int i:posVal) {
        cout<<i<<" ";
    }*/
    for (int i=0;i<N;i++) {
        P[i]=posVal[i];
    }
}

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