Submission #707302

#	Time	Username	Problem	Language	Result	Execution time	Memory
707302		600Mihnea	Koala Game (APIO17_koala)	C++17	37 / 100	81 ms	464 KiB

koala

#include "koala.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

const int NMAX = 1000 + 7;
int nglob;
int b[NMAX];
int r[NMAX];
int wn[NMAX];
int issmall[NMAX];
int isbig[NMAX];

void print(int a[])
{
    cout << " ---> ";
    for (int i = 0; i < nglob; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
}

void ask()
{
    playRound(b, r);
    for (int i = 0; i < nglob; i++)
    {
        wn[i] = (r[i] > b[i]);
    }
}

int minValue(int n, int w)
{
    nglob = n;
    assert(n < NMAX);
    assert(w < NMAX);
    assert(n == w);
    assert(n % 2 == 0);
    for (int i = 0; i < n; i++)
    {
        b[i] = 0;
    }
    b[3] = 1;
    ask();
    int cnt_lose = 0;
    for (int i = 0; i < n; i++)
    {
        cnt_lose += (wn[i] == 0);
    }
    assert(cnt_lose == 1);
    for (int i = 0; i < n; i++)
    {
        if (wn[i] == 0)
        {
            return i;
        }
    }
    assert(0);
}

int maxValue(int n, int w)
{
    nglob = n;
    assert(n < NMAX);
    assert(w < NMAX);
    assert(n == w);
    assert(n % 2 == 0);
    for (int i = 0; i < n; i++)
    {
        isbig[i] = 1;
    }
    for (auto& val : { 1, 2, 4, 11 })
    {
        for (int i = 0; i < n; i++)
        {
            b[i] = 0;
            if (isbig[i])
            {
                b[i] = val;
            }
        }
        ask();
        for (int i = 0; i < n; i++)
        {
            isbig[i] &= wn[i];
        }
    }
    int cntbig = 0;
    for (int i = 0; i < n; i++)
    {
        cntbig += isbig[i];
    }
    assert(cntbig == 1);
    for (int i = 0; i < n; i++)
    {
        if (isbig[i])
        {
            return i;
        }
    }
    assert(0);
}

int greaterValue(int n, int w)
{
    nglob = n;
    assert(n < NMAX);
    assert(w < NMAX);
    vector<int> v;
    for (int i = 1; i <= 50; i++)
    {
        v.push_back(i);
    }
    v = { 1, 2, 4, 8, 16, 32 };
    int low = 0, high = (int)v.size() - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        int val = v[mid];
        for (int i = 0; i < n; i++)
        {
            b[i] = 0;
        }
        b[0] = b[1] = val;
        ask();
        if (wn[0] && wn[1])
        {
            low = mid + 1;
            continue;
        }
        if (!wn[0] && !wn[1])
        {
            high = mid - 1;
            continue;
        }
        if (wn[0] && !wn[1]) return 0;
        assert(wn[1] && !wn[0]);
        return 1;
    }
    assert(0);
}

int funccmp(int x, int y)
{
    int n = nglob;
    vector<int> v;
    v = { 1, 2, 4, 8, 16, 32 };
    int low = 0, high = (int)v.size() - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        int val = v[mid];
        for (int i = 0; i < n; i++)
        {
            b[i] = 0;
        }
        b[x] = b[y] = val;
        ask();
        if (wn[x] && wn[y])
        {
            low = mid + 1;
            continue;
        }
        if (!wn[x] && !wn[y])
        {
            high = mid - 1;
            continue;
        }
        if (wn[x] && !wn[y]) return 0;
        assert(wn[y] && !wn[x]);
        return 1;
    }
    assert(0);
}

int act[NMAX];

void make(vector<pair<int, int>> v)
{
    int n = nglob;
    for (int it = 0; it < (int)v.size(); it++)
    {
        for (int i = 0; i < n; i++)
        {
            b[i] = 0;
            if (act[i])
            {
                b[i] = v[it].first;
            }
        }
        ask();
        assert(v[it].second == 0 || v[it].second == 1);
        for (int i = 0; i < n; i++)
        {
            if (v[it].second == 0)
            {
                act[i] &= (wn[i] == 0);
            }
            else
            {
                act[i] &= (wn[i] == 1);              
            }
        }
        cout << " ---> ";
        for (int i = 0; i < n; i++)
        {
            if (act[i])
            {
                cout << i << " ";
            }
        }
        cout << "\n";
    }
}

map<pair<int, int>, int > wha;
int sl[NMAX];

void dncsma(int l, int rh)
{
    int n = nglob;
    if (l >= rh)
    {
        if (l == rh)
        {
            //cout << "done " << l << "\n";
            for (int i = 0; i < n; i++)
            {
                if (act[i])
                {
                    //cout << l << " -> " << i << "\n";
                    sl[i] = l;
                }
            }
        }
        return;
    }
    vector<int> cur(n);
    for (int i = 0; i < n; i++)
    {
        cur[i] = act[i];
    }
    int nractive = 0;
    for (int i = 0; i < n; i++)
    {
        nractive += cur[i];
    }
    if (!wha.count({ l, rh }))
    {
      //  cout << "bad!\n";
       // exit(0);
    }
    assert(wha.count({ l, rh }));
    int x = wha[{l, rh}];
    for (int i = 0; i < n; i++)
    {
        b[i] = 0;
        if (cur[i])
        {
            b[i] = x;
        }
    }
    //cout << "wha[make_pair(" << l << ", " << r << ")] = " << x << "; ";
    // cout << l << " " << r << " : " << maximums[loc] << "\n";
#ifdef ONPC
    cout << "if(l == " << l << " && rh == " << rh << ") exit(0);" << "\n";
#endif
    ask();
    int sml = 0, bg = 0;
    for (int i = 0; i < n; i++)
    {
        if (cur[i])
        {
            if (wn[i] == 0)
            {
                sml++;
            }
            else
            {
                bg++;
            }
        }
    }
    assert(sml > 0 && bg > 0);
    vector<int> acu(n);
    for (int i = 0; i < n; i++)
    {
        acu[i] = wn[i];
    }
    for (int i = 0; i < n; i++)
    {
        act[i] = cur[i] & (acu[i] == 0);
    }
    assert(l + sml - 1 + 1 == rh - bg + 1);
#ifndef ONPC
    if (l == 28 && rh == 29) exit(0);
#endif
    dncsma(l, l + sml - 1);
    for (int i = 0; i < n; i++)
    {
        act[i] = cur[i] & (acu[i] == 1);
    }
    dncsma(rh - bg + 1, rh);
    //print(act);
}

 
void dnc(int l, int r)
{
    int n = nglob;
    if (l >= r)
    {
        return;
    }
    vector<int> cur(n);
    for (int i = 0; i < n; i++)
    {
        cur[i] = act[i];
    }
    int nractive = 0;
    for (int i = 0; i < n; i++)
    {
        nractive += cur[i];
    }
    assert(nractive == r - l + 1);
    vector<int> posi;
    for (int x = 1; x <= 100; x++)
    {
        if (x * nractive <= 100)
        {
            posi.push_back(x);
        }
    }
    assert(!posi.empty());
    vector<int> maximums;
    for (int it = 0; it < (int)posi.size(); it++)
    {
        int x = posi[it];
        for (int i = 0; i < n; i++)
        {
            b[i] = 0;
            if (cur[i])
            {
                b[i] = x;
            }
        }
        ask();
        int sml = 0, bg = 0;
        for (int i = 0; i < n; i++)
        {
            if (cur[i])
            {
                if (wn[i] == 0)
                {
                    sml++;
                }
                else
                {
                    bg++;
                }
            }
        }
        maximums.push_back(max(sml, bg));
    }
    int min_max = *min_element(maximums.begin(), maximums.end());
    assert(min_max < r - l + 1);
    int loc = min_element(maximums.begin(), maximums.end()) - maximums.begin();
    int x = posi[loc];
    for (int i = 0; i < n; i++)
    {
        b[i] = 0;
        if (cur[i])
        {
            b[i] = x;
        }
    }
    cout << "wha[make_pair(" << l << ", " << r << ")] = " << x << "; ";

   // cout << l << " " << r << " : " << maximums[loc] << "\n";
    ask();
    int sml = 0, bg = 0;
    for (int i = 0; i < n; i++)
    {
        if (cur[i])
        {
            if (wn[i] == 0)
            {
                sml++;
            }
            else
            {
                bg++;
            }
        }
    }
    assert(sml > 0 && bg > 0);
    vector<int> acu(n);
    for (int i = 0; i < n; i++)
    {
        acu[i] = wn[i];
    }
    for (int i = 0; i < n; i++)
    {
        act[i] = cur[i] & (acu[i] == 0);
    }
    assert(l + sml - 1 + 1 == r - bg + 1);
    dnc(l, l + sml - 1);
    for (int i = 0; i < n; i++)
    {
        act[i] = cur[i] & (acu[i] == 1);
    }

    if (l == 94 && r == 96 && 0)
    {
        cout << "dnc " << x << " : " << sml << " and " << bg << "\n";
        cout << "seg = " << r - bg + 1 << " " << r << "\n";
        exit(0);
    }
    dnc(r - bg + 1, r);
    //print(act);
}

void allValues(int n, int w, int* p)
{
    nglob = n;
    assert(n < NMAX);
    assert(w < NMAX);
    if (w == 2 * n)
    {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
    else
    {

        //cout << "salut!\n";
        assert(w == n);
        vector<pair<int, int>> lol;
        for (int i = 0; i < n; i++)
        {
            act[i] = 1;
        }
        wha[make_pair(0, 99)] = 1; wha[make_pair(0, 49)] = 1; wha[make_pair(0, 24)] = 1; wha[make_pair(0, 12)] = 1; wha[make_pair(0, 6)] = 1; wha[make_pair(0, 3)] = 1; wha[make_pair(0, 1)] = 1; wha[make_pair(2, 3)] = 2; wha[make_pair(4, 6)] = 2; wha[make_pair(5, 6)] = 2; wha[make_pair(7, 12)] = 2; wha[make_pair(7, 9)] = 2; wha[make_pair(8, 9)] = 3; wha[make_pair(10, 12)] = 2; wha[make_pair(11, 12)] = 3; wha[make_pair(13, 24)] = 2; wha[make_pair(13, 18)] = 3; wha[make_pair(13, 15)] = 3; wha[make_pair(14, 15)] = 3; wha[make_pair(16, 18)] = 3; wha[make_pair(17, 18)] = 4; wha[make_pair(19, 24)] = 3; wha[make_pair(19, 21)] = 3; wha[make_pair(20, 21)] = 4; wha[make_pair(22, 24)] = 3; wha[make_pair(23, 24)] = 4; wha[make_pair(25, 49)] = 2; wha[make_pair(25, 36)] = 2; wha[make_pair(25, 29)] = 3; wha[make_pair(25, 26)] = 4; wha[make_pair(27, 29)] = 4; wha[make_pair(28, 29)] = 5; wha[make_pair(30, 36)] = 3; wha[make_pair(30, 32)] = 4; wha[make_pair(31, 32)] = 5; wha[make_pair(33, 36)] = 4; wha[make_pair(33, 34)] = 5; wha[make_pair(35, 36)] = 5; wha[make_pair(37, 49)] = 3; wha[make_pair(37, 43)] = 3; wha[make_pair(37, 39)] = 4; wha[make_pair(38, 39)] = 5; wha[make_pair(40, 43)] = 5; wha[make_pair(40, 41)] = 6; wha[make_pair(42, 43)] = 6; wha[make_pair(44, 49)] = 4; wha[make_pair(44, 46)] = 4; wha[make_pair(45, 46)] = 6; wha[make_pair(47, 49)] = 5; wha[make_pair(48, 49)] = 6; wha[make_pair(50, 99)] = 2; wha[make_pair(50, 74)] = 2; wha[make_pair(50, 59)] = 3; wha[make_pair(50, 53)] = 5; wha[make_pair(50, 51)] = 6; wha[make_pair(52, 53)] = 6; wha[make_pair(54, 59)] = 5; wha[make_pair(54, 56)] = 5; wha[make_pair(55, 56)] = 6; wha[make_pair(57, 59)] = 5; wha[make_pair(58, 59)] = 7; wha[make_pair(60, 74)] = 3; wha[make_pair(60, 66)] = 4; wha[make_pair(60, 62)] = 5; wha[make_pair(61, 62)] = 7; wha[make_pair(63, 66)] = 6; wha[make_pair(63, 64)] = 7; wha[make_pair(65, 66)] = 7; wha[make_pair(67, 74)] = 4; wha[make_pair(67, 70)] = 6; wha[make_pair(67, 68)] = 7; wha[make_pair(69, 70)] = 7; wha[make_pair(71, 74)] = 6; wha[make_pair(71, 72)] = 7; wha[make_pair(73, 74)] = 7; wha[make_pair(75, 99)] = 3; wha[make_pair(75, 87)] = 4; wha[make_pair(75, 81)] = 5; wha[make_pair(75, 78)] = 6; wha[make_pair(75, 76)] = 7; wha[make_pair(77, 78)] = 8; wha[make_pair(79, 81)] = 6; wha[make_pair(80, 81)] = 8; wha[make_pair(82, 87)] = 5; wha[make_pair(82, 84)] = 6; wha[make_pair(83, 84)] = 8; wha[make_pair(85, 87)] = 6; wha[make_pair(86, 87)] = 8; wha[make_pair(88, 99)] = 4; wha[make_pair(88, 93)] = 6; wha[make_pair(88, 90)] = 6; wha[make_pair(89, 90)] = 8; wha[make_pair(91, 93)] = 6; wha[make_pair(92, 93)] = 8; wha[make_pair(94, 99)] = 6; wha[make_pair(94, 96)] = 6; wha[make_pair(95, 96)] = 8; wha[make_pair(97, 99)] = 6; wha[make_pair(98, 99)] = 8;
        assert(n == 100);
        dncsma(0, n - 1);
        for (int i = 0; i < n; i++)
        {
            p[i] = sl[i];
        }
        return;
        exit(0);
        lol.push_back({ 1, 1 });
        lol.push_back({ 2, 0 });
        make(lol);
        //for (auto& val : { 1 })
        //{
        //    for (int i = 0; i < n; i++)
        //    {
        //        b[i] = 0;
        //        if (issmall[i])
        //        {
        //            b[i] = val;
        //        }
        //    }
        //    ask();
        //    for (int i = 0; i < n; i++)
        //    {
        //        issmall[i] &= !wn[i];
        //    }
        //    cout << " : ";
        //    for (int i = 0; i < n; i++)
        //    {
        //        if (issmall[i])
        //        {
        //            cout << i << " ";
        //        }
        //    }
        //    cout << "\n";
        //}
        return;
        iota(p, p + n, 0);
        sort(p, p + n, funccmp);
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

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