Submission #1209062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209062		jasonic	Koala Game (APIO17_koala)	C++20	74 / 100	35 ms	464 KiB

koala

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

using namespace std;

const int MXN = 100;
int toSend[MXN];
int response[MXN];

int minValue(int n, int w) {

    toSend[0] = 1;

    playRound(toSend, response);

    for(int i = 1; i < MXN; i++) {
        if(response[i] == 0) return i;
    }
    
    return 0;
}

int maxValue(int n, int w) {
    vector<int> candidates;
    for(int i = 0; i < MXN; i++) candidates.push_back(i);
    
    while(candidates.size() != 1) {
        int cnt = w / candidates.size();
        fill(toSend, toSend + MXN, 0);
        for(auto i : candidates) toSend[i] = cnt;
        playRound(toSend, response);
        candidates.clear();
        for(int i = 0; i < MXN; i++) if(response[i] > cnt) candidates.push_back(i);
    }

    return candidates[0];
}

int greaterValue(int n, int w) {
    int l = 0;
    int r = 10;

    while (l + 1 < r) {
        int m = (l+r)/2;
        toSend[0] = m;
        toSend[1] = m;
        playRound(toSend, response);

        if(response[0] <= m && response[1] <= m) {
            r = m;
        } else if(response[0] > m && response[1] > m) {
            l = m;
        } else {
            return response[0] < response[1];
        }
    }

    toSend[0] = r;
    toSend[1] = r;
    playRound(toSend, response);

    return response[0] < response[1];
}

int S[100];

bool compare1(int a, int b) {
    fill(toSend, toSend + MXN, 0);
    toSend[a] = 100;
    toSend[b] = 100;

    playRound(toSend, response);
    return response[a] < response[b];
}

bool compare2(int a, int b) {
    int l = 0;
    int r = 10;

    while (l + 1 < r) {
        int m = (l+r)/2;
        fill(toSend, toSend + MXN, 0);
        toSend[a] = m;
        toSend[b] = m;
        playRound(toSend, response);

        if(response[a] <= m && response[b] <= m) {
            r = m;
        } else if(response[a] > m && response[b] > m) {
            l = m;
        } else {
            return response[a] < response[b];
        }
    }

    toSend[a] = r;
    toSend[b] = r;
    playRound(toSend, response);

    return response[a] < response[b];
}


void conquer1(int l_l, int l_r, int r_l, int r_r) {
    queue<int> a, b, c;
    for(int i = l_l; i <= l_r; i++) a.push(S[i]);
    for(int i = r_l; i <= r_r; i++) b.push(S[i]);

    while(!a.empty() && !b.empty()) {
        if(compare1(a.front(), b.front())) {
            c.push(a.front());
            a.pop();
        } else {
            c.push(b.front());
            b.pop();
        }
    }

    while(!a.empty()) {
        c.push(a.front());
        a.pop();
    }

    while(!b.empty()) {
        c.push(b.front());
        b.pop();
    }

    for(int i = l_l; i <= r_r; i++) {
        S[i] = c.front();
        c.pop();
    }
}

void conquer2(int l_l, int l_r, int r_l, int r_r) {
    queue<int> a, b, c;
    for(int i = l_l; i <= l_r; i++) a.push(S[i]);
    for(int i = r_l; i <= r_r; i++) b.push(S[i]);

    while(!a.empty() && !b.empty()) {
        if(compare2(a.front(), b.front())) {
            c.push(a.front());
            a.pop();
        } else {
            c.push(b.front());
            b.pop();
        }
    }

    while(!a.empty()) {
        c.push(a.front());
        a.pop();
    }

    while(!b.empty()) {
        c.push(b.front());
        b.pop();
    }

    for(int i = l_l; i <= r_r; i++) {
        S[i] = c.front();
        c.pop();
    }
}


void divide1(int l, int r) {
    if(l != r) {
        int m = l + (r-l)/2;
        divide1(l, m);
        divide1(m+1, r);
        conquer1(l, m, m+1, r);
    }
}

void divide2(int l, int r) {
    if(l != r) {
        int m = l + (r-l)/2;
        divide2(l, m);
        divide2(m+1, r);
        conquer2(l, m, m+1, r);
    }
}


void allValues(int n, int w, int *p) {
    if (w == 2*n) {
        for(int i = 0; i < n; i++) S[i] = i;
        divide1(0, n-1); // S is now sorted in order of the indices with increasing value
        
        for(int i = 0; i < n; i++) p[S[i]] = i+1;
    } else {
        for(int i = 0; i < n; i++) S[i] = i;
        divide2(0, n-1); // S is now sorted in order of the indices with increasing value
        
        for(int i = 0; i < n; i++) p[S[i]] = i+1;
    }
}

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