Submission #52174

#	Time	Username	Problem	Language	Result	Execution time	Memory
52174		imeimi2000	Koala Game (APIO17_koala)	C++17	100 / 100	152 ms	940 KiB

koala

#include "koala.h"
#include <vector>
#include <set>

using namespace std;

int n, w;
int qb[100];
int qr[100];
int minValue(int N, int W) {
    n = N;
    w = W;
    qb[0] = 1;
    for (int i = 1; i < n; ++i) {
        qb[i] = 0;
    }
    playRound(qb, qr);
    for (int i = 0; i < n; ++i) {
        if (qb[i] < qr[i]) continue;
        return i;
    }
}

int cand[100];
int maxValue(int N, int W) {
    n = N;
    w = W;
    for (int i = 0; i < n; ++i) cand[i] = 1;
    int cnt = n;
    
    while (cnt > 1) {
        for (int i = 0; i < n; ++i) {
            if (cand[i]) qb[i] = w / cnt;
            else qb[i] = 0;
        }
        playRound(qb, qr);
        for (int i = 0; i < n; ++i) {
            if (cand[i] && qr[i] <= qb[i]) --cnt, cand[i] = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (cand[i]) return i;
    }
}

int greaterValue(int N, int W) {
    n = N;
    w = W;
    for (int i = 0; i < n; ++i) {
        qb[i] = 0;
    }
    const int arr[5] = { 1, 2, 3, 5, 8 };
    int s = 0, e = 4;
    while (s <= e) {
        int m = (s + e) / 2;
        qb[0] = qb[1] = arr[m];
        playRound(qb, qr);
        int a = (qb[0] < qr[0]);
        int b = (qb[1] < qr[1]);
        if (a != b) return b;
        if (a) s = m + 1;
        else e = m - 1;
    }
}

int sortArray[100];
bool cmp(int x, int y) {
    for (int i = 0; i < n; ++i) {
        qb[i] = 0;
    }
    qb[x] = qb[y] = n;
    playRound(qb, qr);
    if (qb[x] < qr[x]) return 0;
    return 1;
}

void mergeSort(int s, int e) {
    if (e <= s) return;
    int m = (s + e) / 2;
    mergeSort(s, m);
    mergeSort(m + 1, e);
    int tp[100];
    int i = s, j = m + 1, k = s;
    while (i <= m || j <= e) {
        if (i > m) tp[k++] = sortArray[j++];
        else if (j > e) tp[k++] = sortArray[i++];
        else if (cmp(sortArray[i], sortArray[j])) tp[k++] = sortArray[i++];
        else tp[k++] = sortArray[j++];
    }
    for (i = s; i <= e; ++i) {
        sortArray[i] = tp[i];
    }
}

int saveFinds[101];
int findNineMax(const set<int> &mp) {
    for (int i = 0; i < n; ++i) {
        qb[i] = 0;
    }
    for (int i : mp) qb[i] = 11;
    for (int i = mp.size(); i < 9; ++i) qb[saveFinds[i]] = 11;
    playRound(qb, qr);
    for (int i : mp) {
        if (qb[i] < qr[i]) return i;
    }
}

void findNumbers(int s, int e, int qs = 0) {
    const int qn[3] = { 2, 4, 3 };
    if (e - s < 9) {
        set<int> mp;
        for (int i = s; i <= e; ++i) mp.insert(saveFinds[i]);
        for (int i = e; i > s; --i) {
            mp.erase(saveFinds[i] = findNineMax(mp));
        }
        saveFinds[s] = *mp.begin();
        return;
    }
    for (int i = 0; i < n; ++i) {
        qb[i] = 0;
    }
    for (int i = s; i <= e; ++i) {
        qb[saveFinds[i]] = qn[qs];
    }
    playRound(qb, qr);
    vector<int> tp1, tp2;
    for (int i = s; i <= e; ++i) {
        if (qb[saveFinds[i]] < qr[saveFinds[i]]) tp2.push_back(saveFinds[i]);
        else tp1.push_back(saveFinds[i]);
    }
    int i = s;
    for (int j : tp1) saveFinds[i++] = j;
    for (int j : tp2) saveFinds[i++] = j;
    i = s + tp1.size();
    findNumbers(s, i - 1, qs + 1);
    findNumbers(i, e, qs + 1);
}

void allValues(int N, int W, int *P) {
    n = N;
    w = W;
    if (W == N + N) {
        for (int i = 0; i < n; ++i) {
            sortArray[i] = i;
        }
        mergeSort(0, n - 1);
        for (int i = 0; i < n; ++i) {
            P[sortArray[i]] = i + 1;
        }
    } else {
        int arr[100];
        set<int> mp;
        for (int i = 0; i < n; ++i) mp.insert(i);
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                qb[j] = 0;
                arr[j] = 1;
            }
            for (int j = 0; j < i; ++j) {
                qb[saveFinds[j]] = 1;
                arr[saveFinds[j]] = 0;
            }
            for (int j = 0, k = 0; j < n && k <= i; ++j) {
                if (qb[j]) continue;
                qb[j] = 1;
                ++k;
            }
            playRound(qb, qr);
            for (int j = 0; j < n; ++j) {
                if (arr[j] && qr[j] <= qb[j]) {
                    saveFinds[i] = j;
                    mp.erase(j);
                    break;
                }
            }
        }
        for (int i = n / 2; i < n; ++i) {
            saveFinds[i] = *mp.begin();
            mp.erase(mp.begin());
        }
        findNumbers(n / 2, n - 1);
        for (int i = 0; i < n; ++i) {
            P[saveFinds[i]] = i + 1;
        }
    }
}

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int findNineMax(const std::set<int>&)':
koala.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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