Submission #810506

#	Time	Username	Problem	Language	Result	Execution time	Memory
810506		oscar1f	Koala Game (APIO17_koala)	C++17	88 / 100	39 ms	340 KiB

koala

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

using namespace std;

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;
    int mini=1;
    if (deb>=4 and (fin-deb+1)*2<=100) {
        mini=2;
    }
    for (int i=mini;i<=13;i++) {
        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()) {
            //cout<<deb<<" "<<fin<<" : "<<i<<endl;
            solve(deb,deb+petit.size()-1,petit);
            solve(deb+petit.size(),fin,grand);
            return;
        }
    }
}

bool plusGrand(int a,int b) {
    vector<int> quest(100),rep(100);
    quest[a]=100;
    quest[b]=100;
    rep=jouer(quest);
    if (rep[a]<=100) {
        return true;
    }
    return false;
}

vector<int> trier(vector<int> v) {
    if (v.size()<=1) {
        return v;
    }
    vector<int> a,b;
    for (int i=0;i<(int)v.size()/2;i++) {
        a.push_back(v[i]);
    }
    for (int i=(int)v.size()/2;i<(int)v.size();i++) {
        b.push_back(v[i]);
    }
    v.clear();
    a=trier(a);
    b=trier(b);
    while (!a.empty() or !b.empty()) {
        if (a.empty()) {
            v.push_back(b.back());
            b.pop_back();
        }
        else if (b.empty()) {
            v.push_back(a.back());
            a.pop_back();
        }
        else if (plusGrand(a.back(),b.back())) {
            v.push_back(b.back());
            b.pop_back();
        }
        else {
            v.push_back(a.back());
            a.pop_back();
        }
    }
    reverse(v.begin(),v.end());
    return v;
}

void allValues(int N, int W, int *P) {
    if (W==200) {
        vector<int> ans;
        for (int i=0;i<N;i++) {
            ans.push_back(i);
        }
        ans=trier(ans);
        for (int i=0;i<N;i++) {
            P[ans[i]]=i+1;
        }
        return;
    }
    vector<int> deb;
    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: 10 / 10
• Subtask 5: 41 / 53