Submission #847480

#	Time	Username	Problem	Language	Result	Execution time	Memory
847480		oscar1f	Monster Game (JOI21_monster)	C++17	92 / 100	73 ms	4648 KiB

monster

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

using namespace std;

const int MAX_VAL=1000+5;
int nbVal,nbReq;
int memo[MAX_VAL][MAX_VAL];

int quest(int a,int b) {
    if (a>b) {
        return 1-quest(b,a);
    }
    if (memo[a][b]!=-1) {
        return memo[a][b];
    }
    if (Query(a,b)) {
        memo[a][b]=1;
    }
    else {
        memo[a][b]=0;
    }
    nbReq++;
    return memo[a][b];
}

vector<int> calc(vector<int> pers) {
    int taille=pers.size();
    if (taille==1) {
        return pers;
    }
    int mid=taille/2;
    vector<int> gau,dro,ans;
    for (int i=0;i<mid;i++) {
        gau.push_back(pers[i]);
    }
    for (int i=mid;i<taille;i++) {
        dro.push_back(pers[i]);
    }
    gau=calc(gau);
    dro=calc(dro);
    while (!gau.empty() or !dro.empty()) {
        if (gau.empty()) {
            ans.push_back(dro.back());
            dro.pop_back();
        }
        else if (dro.empty()) {
            ans.push_back(gau.back());
            gau.pop_back();
        }
        else {
            if (quest(gau.back(),dro.back())==1) {
                ans.push_back(gau.back());
                gau.pop_back();
            }
            else {
                ans.push_back(dro.back());
                dro.pop_back();
            }
        }
    }
    reverse(ans.begin(),ans.end());
    /*for (int i:ans) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    return ans;
}

vector<int> Solve(int N) {
    nbVal=N;
    for (int i=0;i<nbVal;i++) {
        for (int j=0;j<nbVal;j++) {
            memo[i][j]=-1;
        }
    }
    vector<int> rep,init,ans;
    for (int i=0;i<nbVal;i++) {
        init.push_back(i);
    }
    srand(time(NULL));
    random_shuffle(init.begin(),init.end());
    rep=calc(init);
    /*for (int i:rep) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    int pos=0,deb,fin;
    while (pos<nbVal) {
        deb=pos;
        if (deb==0) {
            vector<int> listeInf;
            for (int i=1;i<nbVal;i++) {
                if (quest(rep[0],rep[i])==1) {
                    listeInf.push_back(i);
                    //cout<<i<<" ";
                }
            }
            //cout<<endl;
            if (listeInf.size()==1) {
                fin=listeInf.back();
                vector<int> liste2;
                for (int i=0;i<nbVal;i++) {
                    if (i!=fin and quest(rep[fin],rep[i])==1) {
                        liste2.push_back(i);
                    }
                }
                if (liste2.size()==1) {
                    fin=0;
                }
                else {
                    fin=1;
                }
            }
            else {
                listeInf.pop_back();
                fin=listeInf.back();
            }
            pos=fin;
            while (deb<fin) {
                swap(rep[deb],rep[fin]);
                deb++;
                fin--;
            }
        }
        else {
            while (quest(rep[deb-1],rep[pos])==0) {
                pos++;
            }
            fin=pos;
            //cout<<deb<<" "<<fin<<endl;
            while (deb<fin) {
                swap(rep[deb],rep[fin]);
                deb++;
                fin--;
            }
        }
        pos++;
    }
    /*for (int i:rep) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    ans.resize(nbVal);
    for (int i=0;i<nbVal;i++) {
        ans[rep[i]]=i;
    }
    /*for (int i:ans) {
        cout<<i<<" ";
    }
    cout<<endl;
    cout<<"Nombre de questions : "<<nbReq<<endl;*/
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 67 / 75