Submission #49586

#	Time	Username	Problem	Language	Result	Execution time	Memory
49586		model_code	Koala Game (APIO17_koala)	C++17	92 / 100	145 ms	848 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;

#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
#define sz(v) ((int)v.size())

struct Query {
    vector <int> am;
};

struct Response {
    vector <bool> v;
};

int N, W;

Response makeQuery (Query q) {
    int *B = (int *)malloc(sizeof(int)*N);
    FO (i,0,N) B[i] = q.am[i];
    int *R = (int *)malloc(sizeof(int)*N);
    playRound(B,R);
    Response r;
    FO (i,0,N) {
        if (R[i] > B[i]) {
            r.v.pb(true);
        } else {
            r.v.pb(false);
        }
    }
    free(B);
    free(R);
    return r;
}

Response makeUniformQuery (set<int> &cand, int am) {
    Query q;
    FO (i,0,N) {
        if (cand.find(i) != cand.end()) {
            q.am.pb(am);
        } else {
            q.am.pb(0);
        }
    }
    return makeQuery(q);
}

set<int> responseToSet (Response r) {
    set <int> s;
    FO (i,0,N) if (r.v[i]) s.insert(i);
    return s;
}

int minValue(int _N, int _W) {
    N = _N; W = _W;
    set <int> cand;
    cand.insert(0);
    Response r = makeUniformQuery(cand, 1);
    FO (i,0,N) {
        if (!r.v[i]) return i;
    }
    assert (false);
}

int actualGetMax() {
    set <int> cand;
    FO (i,0,N) cand.insert(i);
    while (cand.size() > 1) {
        Response r = makeUniformQuery(cand, W/(int)cand.size());
        set <int> newC;
        FO (i,0,N) if (cand.find(i) != cand.end() && r.v[i]) newC.insert(i);
        cand = newC;
    }
    return *(cand.begin());
}

int maxValue(int _N, int _W) {
    N = _N; W = _W;
    return actualGetMax();
}

int greaterValue(int _N, int _W) {
    N = _N; W = _W;
    set <int> f2 = {0,1};
    int cands[4] = {1,3,6,8};
    int lo = 0;
    int hi = 3;
    int mid;
    while (lo <= hi) {
        mid = (lo+hi)/2;
        Response r = makeUniformQuery(f2, cands[mid]);
        set <int> origRes = responseToSet(r);
        set <int> res;
        for (auto c : f2) {
            if (origRes.find(c) != origRes.end()) res.insert(c);
        }
        switch (res.size()) {
            case 0:
                hi = mid-1;
                break;
            case 1:
                return *(res.begin());
            case 2:
                lo = mid+1;
                break;
        }
    }
    assert(false);
}

vector <int> sortRange (vector <int> vals);
void solveMain(int *P);
void allValues(int _N, int _W, int *P) {
    N = _N; W = _W;
    if (_W == 2*_N) {
        vector <int> startVals;
        FO (i,0,N) startVals.pb(i);
        vector <int> endVals = sortRange(startVals);
        FO (i,0,N) P[endVals[i]] = N-i;
    } else {
        solveMain(P);
    }
}

// returns greater of the 2
int sub4cmp(int a, int b) {
    set<int> vals = {a,b};
    set<int> takens = responseToSet(makeUniformQuery(vals, W/2));
    if (takens.find(a) != takens.end()) return a;
    else return b;
}

vector <int> sortRange (vector <int> vals) {
    if (vals.size() == 1) return vals;
    vector <int> fV, sV;
    FO (i,0,sz(vals)) {
        if (i%2) sV.pb(vals[i]);
        else fV.pb(vals[i]);
    }
    vector <int> sF = sortRange(fV);
    vector <int> sS = sortRange(sV);
    int fI(0), sI(0);
    vector <int> retV;
    while (fI < sz(sF) || sI < sz(sS)) {
        if (fI == sz(sF)) retV.pb(sS[sI++]);
        else if (sI == sz(sS)) retV.pb(sF[fI++]);
        else {
            if (sub4cmp(sF[fI], sS[sI]) == sF[fI]) {
                retV.pb(sF[fI++]);
            } else {
                retV.pb(sS[sI++]);
            }
        }
    }
    return retV;
}

set <int> lowestVals;
#define N_BUCKETS 9
#define B_SIZ 10
vector <int> startBuckets[N_BUCKETS];
vector <int> sortedB[N_BUCKETS];
int valToPos[105];

int maxInSet(set<int> &s) {
    // Need this:
    assert(s.size() <= 9);
    set<int> qSet(s);
    for (int i = 10; i >= 1; i--) {
        if (qSet.size() == 9) break;
        qSet.insert(valToPos[i]);
    }
    set<int> taken;
    if (s.size() == 1) {
        taken = responseToSet(makeUniformQuery(qSet, 10));
    } else {
        taken = responseToSet(makeUniformQuery(qSet, 11));
    }
    for (int v : s) {
        if (taken.find(v) != taken.end()) return v;
    }
    assert(false);
}

void solveMain (int *P) {
    lowestVals.clear();
    FO (i,0,N_BUCKETS) {
        startBuckets[i].clear();
        sortedB[i].clear();
    }
    int mx = actualGetMax();
    set<int> mxSet({mx});
    set<int> notLowestVals = 
        responseToSet(makeUniformQuery(mxSet, 10));
    FO (i,0,N) {
        if (notLowestVals.count(i) == 0) lowestVals.insert(i);
    }
    assert(lowestVals.size() == 10);
    FO (i,0,N) {
        if (lowestVals.find(i) != lowestVals.end()) continue;
        FO (b,0,N_BUCKETS) {
            if (startBuckets[b].size() < B_SIZ) {
                startBuckets[b].pb(i);
                break;
            }
        }
    }
    // Get bottom 10:
    set <int> lowLeft (lowestVals);
    while (lowLeft.size()) {
        if (lowLeft.size() == 1) {
            valToPos[1] = *lowLeft.begin();
            break;
        }
        set <int> res =
            responseToSet(makeUniformQuery(lowLeft, lowLeft.size()-1));
        for (int v : res) {
            if (lowLeft.find(v) != lowLeft.end()) {
                valToPos[lowLeft.size()] = v;
                lowLeft.erase(v);
                break;
            }
        }
    }
    FO (b,0,N_BUCKETS) {
        set <int> remThings(startBuckets[b].begin(), startBuckets[b].end());
        while (remThings.size()) {
            if (remThings.size() == 10) {
                // one special case:
                set <int> res = responseToSet(makeUniformQuery(remThings, 10));
                set <int> cMax;
                for (int v : res) {
                    if (remThings.find(v) != remThings.end()) {
                        cMax.insert(v);
                    }
                }
                if (cMax.size() == 2) {
                    int mx = maxInSet(cMax);
                    sortedB[b].pb(mx);
                    cMax.erase(mx);
                    sortedB[b].pb(*cMax.begin());
                    remThings.erase(mx);
                    remThings.erase(*cMax.begin());
                } else if (cMax.size() == 1) {
                    sortedB[b].pb(*cMax.begin());
                    remThings.erase(*cMax.begin());
                } else {
                    assert(false);
                }
            } else {
                int mx;
                if (remThings.size() == 1) mx = *remThings.begin();
                else mx = maxInSet(remThings);
                sortedB[b].pb(mx);
                remThings.erase(mx);
            }
        }
    }
    // Merge buckets:
    // Sort buckets into increasing order not decreasing:
    FO (i,0,N_BUCKETS) reverse(sortedB[i].begin(), sortedB[i].end());
    vector <int> sortedAll;
    while(true) {
        set <int> cFronts;
        FO (i,0,N_BUCKETS) {
            if (sortedB[i].size()) {
                cFronts.insert(sortedB[i].back());
            }
        }
        if (cFronts.empty()) break;
        int mx = maxInSet(cFronts);
        sortedAll.pb(mx);
        FO (i,0,N_BUCKETS) {
            if (sortedB[i].size() && sortedB[i].back() == mx) {
                sortedB[i].pop_back();
            }
        }
    }
    for (int i = 10; i >= 1; i--) {
        sortedAll.pb(valToPos[i]);
    }
    FO (i,0,sz(sortedAll)) {
        P[sortedAll[i]] = N-i;
    }
}

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