Submission #919422

#	Time	Username	Problem	Language	Result	Execution time	Memory
919422		vnm06	Koala Game (APIO17_koala)	C++14	75 / 100	40 ms	600 KiB

koala

#include "koala.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
 
typedef long long llong;
const int MAXN = 128;
const int INF =  1e9;
 
int n, w;
int __b[MAXN];
int __r[MAXN];
std::vector <int> play(const std::vector <int> &b)
{
    assert(b.size() == n);
    for (int i = 0 ; i < n ; ++i)
    {
        __b[i] = b[i];
    }
 
    playRound(__b, __r);
    std::vector <int> r(n);
    for (int i = 0 ; i < n ; ++i)
    {
        r[i] = __r[i];
    }
 
    return r;
}
 
int minValue(int N, int W) 
{
    n = N; w = W;
    std::vector <int> askFor(n, 0);
    askFor[0] = 1;
 
    std::vector <int> r = play(askFor);
    for (int i = 0 ; i < N ; ++i)
    {
        if (r[i] == 0)
        {
            return i;
        }
    }
 
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}
 
int maxValue(int N, int W) 
{
    n = N; w = W;
    int step = 0;
    std::vector <int> candidates(n);
    std::iota(candidates.begin(), candidates.end(), 0);
    while (candidates.size() > 1)
    {
        step++;
        std::vector <int> b(n, 0);
        for (const int &pos : candidates)
        {
            b[pos] = w / candidates.size();
        }
 
        // step = 2 * step;
        std::vector <int> r = play(b);
        std::vector <int> newCandidates;
        for (const int &pos : candidates)
        {
            if (r[pos] > b[pos])
            {
                newCandidates.push_back(pos);
            }
        }
 
        candidates = newCandidates;
    }
 
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return candidates[0];
}
 
int knownValues[MAXN];
bool cmp(int x, int y)
{
    if (knownValues[x] != 0 && knownValues[y] != 0)
    {
        return (knownValues[x] < knownValues[y]);
    }
 
    if (knownValues[x] != 0)
    {
        return true;
    }
    
    if (knownValues[y] != 0)
    {
        return false;
    }
    
    int times = 0;
    int l = 1, rr = 9, mid;
    while (l + 1 < rr)
    {
        times++;
        mid =  l + (rr - l + 1) / 2 + 2 * (rr - l == 8) + (l == 1 && rr == 6);
        std::vector <int> b(n, 0);
        b[x] = b[y] = mid;
    
        std::vector <int> r = play(b);
        if (r[x] > b[x] && r[y] <= b[y]) return false;
        if (r[y] > b[y] && r[x] <= b[x]) return true;
        if (r[x] <= b[x]) rr = mid;
        else l = mid;
    }
 
    std::vector <int> b(n, 0);
    b[x] = b[y] = 1;
    std::vector <int> r = play(b);
    if (r[x] > b[x] && r[y] <= b[y]) return false;
    if (r[y] > b[y] && r[x] <= b[x]) return true;
    assert(false);
}
 
int greaterValue(int N, int W) 
{
    n = N; w = W;
    int x = 0, y = 1;
    int times = 0;
    int l = 0, rr = 13, mid;
    while (l + 1 < rr)
    {
        times++;
        mid = (l + rr) / 2 + ((rr - l) % 2 == 1);
        std::vector <int> b(n, 0); 
        b[x] = b[y] = mid;
    
        std::vector <int> r = play(b);
        if (r[x] > b[x] && r[y] <= b[y]) return false;
        if (r[y] > b[y] && r[x] <= b[x]) return true;
        if (r[x] <= b[x]) rr = mid;
        else l = mid;
    }
 
    assert(false);
}
 
bool sigmaCMP(int x, int y)
{
    std::vector <int> b(n, 0);
    b[x] = b[y] = w / 2;
    std::vector <int> r = play(b);
    if (r[x] > n) return false;
    return true;
}
 
int toSort[MAXN];
int cpy[MAXN];
 
void sigmaMerge(int l, int r)
{
    if (l == r)
    {
        return;
    }
 
    int mid = (l + r) / 2;
    sigmaMerge(l, mid);
    sigmaMerge(mid + 1, r);
 
    int lPtr = l, rPtr = mid + 1, ptr = l;
    while (lPtr <= mid || rPtr <= r)
    {
        if (lPtr == mid + 1)
        {
            cpy[ptr++] = toSort[rPtr++];
            continue;
        }
 
        if (rPtr == r + 1)
        {
            cpy[ptr++] = toSort[lPtr++];
            continue;
        }
 
        if (sigmaCMP(toSort[lPtr], toSort[rPtr]))
        {
            cpy[ptr++] = toSort[lPtr++];
        } else
        {
            cpy[ptr++] = toSort[rPtr++];
        }
    }
 
    for (int i = l ; i <= r ; ++i)
    {
        toSort[i] = cpy[i];
    }
}   
 
void merge(int l, int r)
{
    if (l == r)
    {
        return;
    }
 
    int mid = (l + r) / 2;
    merge(l, mid);
    merge(mid + 1, r);
 
    int lPtr = l, rPtr = mid + 1, ptr = l;
    while (lPtr <= mid || rPtr <= r)
    {
        if (lPtr == mid + 1)
        {
            cpy[ptr++] = toSort[rPtr++];
            continue;
        }
 
        if (rPtr == r + 1)
        {
            cpy[ptr++] = toSort[lPtr++];
            continue;
        }
 
        if (cmp(toSort[lPtr], toSort[rPtr]))
        {
            cpy[ptr++] = toSort[lPtr++];
        } else
        {
            cpy[ptr++] = toSort[rPtr++];
        }
    }
 
    for (int i = l ; i <= r ; ++i)
    {
        toSort[i] = cpy[i];
    }
}   
 
std::mt19937 rng(69420);
void allValues(int N, int W, int *res) 
{
    n = N; w = W;
    if (W == 2*N) 
    {
        std::iota(toSort, toSort + n, 0);
        sigmaMerge(0, n - 1);
        for (int i = 0 ; i < n ; ++i)
        {
            res[toSort[i]] = i + 1;
        }
 
    } else {
        std::iota(toSort, toSort + n, 0);
        std::shuffle(toSort, toSort + n, rng);
        std::fill(knownValues, knownValues + n, 0);
 
        int c = 13;
        for (int i = 1 ; i <= c ; ++i)
        {
            while (true)
            {
                int pos;
                do pos = rng() % n;
                while (knownValues[pos]);
 
                std::vector <int> b(n, 0);
                b[pos] = i;
                std::vector <int> r = play(b);
                if (r[pos] > b[pos])
                {
                    for (int j = 0 ; j < n ; ++j)
                    {
                        if (knownValues[j] == 0 && r[j] == 0)
                        {
                            knownValues[j] = i;
                            break;
                        }
                    }
 
                    break;
                }
            }
        }
 
        merge(0, n - 1);
 
        for (int i = 0 ; i < n ; ++i)
        {
            res[toSort[i]] = i + 1;
        }
 
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from koala.cpp:5:
koala.cpp: In function 'std::vector<int> play(const std::vector<int>&)':
koala.cpp:18:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     assert(b.size() == n);
      |            ~~~~~~~~~^~~~

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