Submission #707306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707306	2023-03-08T18:19:54 Z	600Mihnea	Koala Game (APIO17_koala)	C++17	100 / 100	70 ms	472 KB

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 + 1;
                }
            }
        }
        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 == 2 && rh == 3) 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 <= 200)
        {
            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.        
        for (int i = 0; i < n; i++)
        {
            act[i] = 1;
        }
        wha[make_pair(0, 99)] = 2; wha[make_pair(0, 33)] = 5; wha[make_pair(0, 11)] = 16; wha[make_pair(0, 5)] = 26; wha[make_pair(0, 2)] = 34; wha[make_pair(1, 2)] = 51; wha[make_pair(3, 5)] = 35; wha[make_pair(4, 5)] = 52; wha[make_pair(6, 11)] = 27; wha[make_pair(6, 8)] = 35; wha[make_pair(7, 8)] = 52; wha[make_pair(9, 11)] = 35; wha[make_pair(10, 11)] = 53; wha[make_pair(12, 33)] = 9; wha[make_pair(12, 21)] = 19; wha[make_pair(12, 16)] = 27; wha[make_pair(12, 13)] = 53; wha[make_pair(14, 16)] = 35; wha[make_pair(15, 16)] = 53; wha[make_pair(17, 21)] = 27; wha[make_pair(17, 18)] = 53; wha[make_pair(19, 21)] = 36; wha[make_pair(20, 21)] = 53; wha[make_pair(22, 33)] = 16; wha[make_pair(22, 27)] = 28; wha[make_pair(22, 24)] = 36; wha[make_pair(23, 24)] = 54; wha[make_pair(25, 27)] = 36; wha[make_pair(26, 27)] = 54; wha[make_pair(28, 33)] = 28; wha[make_pair(28, 30)] = 36; wha[make_pair(29, 30)] = 54; wha[make_pair(31, 33)] = 36; wha[make_pair(32, 33)] = 54; wha[make_pair(34, 99)] = 3; wha[make_pair(34, 54)] = 9; wha[make_pair(34, 42)] = 19; wha[make_pair(34, 37)] = 37; wha[make_pair(34, 35)] = 54; wha[make_pair(36, 37)] = 55; wha[make_pair(38, 42)] = 28; wha[make_pair(38, 39)] = 55; wha[make_pair(40, 42)] = 37; wha[make_pair(41, 42)] = 55; wha[make_pair(43, 54)] = 15; wha[make_pair(43, 47)] = 28; wha[make_pair(43, 44)] = 55; wha[make_pair(45, 47)] = 37; wha[make_pair(46, 47)] = 55; wha[make_pair(48, 54)] = 23; wha[make_pair(48, 50)] = 37; wha[make_pair(49, 50)] = 55; wha[make_pair(51, 54)] = 37; wha[make_pair(51, 52)] = 55; wha[make_pair(53, 54)] = 55; wha[make_pair(55, 99)] = 4; wha[make_pair(55, 67)] = 15; wha[make_pair(55, 60)] = 29; wha[make_pair(55, 57)] = 37; wha[make_pair(56, 57)] = 56; wha[make_pair(58, 60)] = 37; wha[make_pair(59, 60)] = 56; wha[make_pair(61, 67)] = 23; wha[make_pair(61, 63)] = 37; wha[make_pair(62, 63)] = 56; wha[make_pair(64, 67)] = 38; wha[make_pair(64, 65)] = 56; wha[make_pair(66, 67)] = 56; wha[make_pair(68, 99)] = 6; wha[make_pair(68, 79)] = 15; wha[make_pair(68, 72)] = 29; wha[make_pair(68, 69)] = 56; wha[make_pair(70, 72)] = 38; wha[make_pair(71, 72)] = 56; wha[make_pair(73, 79)] = 23; wha[make_pair(73, 75)] = 38; wha[make_pair(74, 75)] = 56; wha[make_pair(76, 79)] = 38; wha[make_pair(76, 77)] = 56; wha[make_pair(78, 79)] = 57; wha[make_pair(80, 99)] = 10; wha[make_pair(80, 87)] = 24; wha[make_pair(80, 83)] = 38; wha[make_pair(80, 81)] = 57; wha[make_pair(82, 83)] = 57; wha[make_pair(84, 87)] = 38; wha[make_pair(84, 85)] = 57; wha[make_pair(86, 87)] = 57; wha[make_pair(88, 99)] = 15; wha[make_pair(88, 92)] = 29; wha[make_pair(88, 89)] = 57; wha[make_pair(90, 92)] = 38; wha[make_pair(91, 92)] = 57; wha[make_pair(93, 99)] = 24; wha[make_pair(93, 95)] = 38; wha[make_pair(94, 95)] = 57; wha[make_pair(96, 99)] = 39; wha[make_pair(96, 97)] = 57; wha[make_pair(98, 99)] = 57;
        dncsma(0, n - 1);
        for (int i = 0; i < n; i++)
        {
            p[i] = sl[i];
        }
        return;
    }
    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)] = 1; wha[make_pair(4, 6)] = 1; wha[make_pair(5, 6)] = 2; wha[make_pair(7, 12)] = 2; wha[make_pair(7, 9)] = 2; wha[make_pair(8, 9)] = 2; wha[make_pair(10, 12)] = 2; wha[make_pair(11, 12)] = 3; wha[make_pair(13, 24)] = 2; wha[make_pair(13, 18)] = 2; wha[make_pair(13, 14)] = 3; wha[make_pair(15, 18)] = 3; wha[make_pair(15, 16)] = 3; wha[make_pair(17, 18)] = 3; 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, 37)] = 2; wha[make_pair(25, 29)] = 3; wha[make_pair(25, 26)] = 4; wha[make_pair(27, 29)] = 3; wha[make_pair(28, 29)] = 4; wha[make_pair(30, 37)] = 3; wha[make_pair(30, 33)] = 4; wha[make_pair(30, 31)] = 5; wha[make_pair(32, 33)] = 5; wha[make_pair(34, 37)] = 4; wha[make_pair(34, 35)] = 5; wha[make_pair(36, 37)] = 5; wha[make_pair(38, 49)] = 3; wha[make_pair(38, 43)] = 4; wha[make_pair(38, 40)] = 4; wha[make_pair(39, 40)] = 5; wha[make_pair(41, 43)] = 4; wha[make_pair(42, 43)] = 5; wha[make_pair(44, 49)] = 4; wha[make_pair(44, 46)] = 4; wha[make_pair(45, 46)] = 6; wha[make_pair(47, 49)] = 4; 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)] = 4; wha[make_pair(54, 56)] = 5; wha[make_pair(55, 56)] = 6; wha[make_pair(57, 59)] = 5; wha[make_pair(58, 59)] = 6; wha[make_pair(60, 74)] = 3; wha[make_pair(60, 66)] = 4; wha[make_pair(60, 62)] = 5; wha[make_pair(61, 62)] = 6; wha[make_pair(63, 66)] = 5; wha[make_pair(63, 64)] = 7; wha[make_pair(65, 66)] = 7; wha[make_pair(67, 74)] = 4; wha[make_pair(67, 70)] = 5; 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)] = 4; wha[make_pair(75, 77)] = 6; wha[make_pair(76, 77)] = 7; wha[make_pair(78, 81)] = 6; wha[make_pair(78, 79)] = 7; wha[make_pair(80, 81)] = 7; wha[make_pair(82, 87)] = 5; wha[make_pair(82, 84)] = 6; wha[make_pair(83, 84)] = 7; wha[make_pair(85, 87)] = 6; wha[make_pair(86, 87)] = 8; wha[make_pair(88, 99)] = 4; wha[make_pair(88, 93)] = 5; 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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	4 ms	336 KB	Output is correct
3	Correct	4 ms	336 KB	Output is correct
4	Correct	4 ms	208 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	336 KB	Output is correct
2	Correct	11 ms	336 KB	Output is correct
3	Correct	12 ms	336 KB	Output is correct
4	Correct	10 ms	336 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	472 KB	Output is correct
2	Correct	69 ms	340 KB	Output is correct
3	Correct	62 ms	340 KB	Output is correct
4	Correct	63 ms	336 KB	Output is correct
5	Correct	63 ms	336 KB	Output is correct
6	Correct	65 ms	348 KB	Output is correct
7	Correct	68 ms	340 KB	Output is correct
8	Correct	65 ms	336 KB	Output is correct
9	Correct	62 ms	340 KB	Output is correct
10	Correct	61 ms	348 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	336 KB	Output is correct
2	Correct	6 ms	464 KB	Output is correct
3	Correct	5 ms	336 KB	Output is correct
4	Correct	6 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	5 ms	336 KB	Output is correct
7	Correct	5 ms	336 KB	Output is correct
8	Correct	5 ms	336 KB	Output is correct
9	Correct	5 ms	336 KB	Output is correct
10	Correct	5 ms	336 KB	Output is correct
11	Correct	5 ms	344 KB	Output is correct
12	Correct	5 ms	336 KB	Output is correct
13	Correct	5 ms	336 KB	Output is correct
14	Correct	6 ms	336 KB	Output is correct
15	Correct	5 ms	336 KB	Output is correct
16	Correct	5 ms	336 KB	Output is correct
17	Correct	6 ms	336 KB	Output is correct
18	Correct	6 ms	336 KB	Output is correct
19	Correct	6 ms	336 KB	Output is correct
20	Correct	6 ms	336 KB	Output is correct

Subtask #5

53.0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	336 KB	Output is correct
2	Correct	3 ms	336 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	3 ms	336 KB	Output is correct
5	Correct	3 ms	336 KB	Output is correct
6	Correct	3 ms	336 KB	Output is correct
7	Correct	3 ms	336 KB	Output is correct
8	Correct	3 ms	336 KB	Output is correct
9	Correct	3 ms	336 KB	Output is correct
10	Correct	3 ms	336 KB	Output is correct
11	Correct	3 ms	336 KB	Output is correct
12	Correct	3 ms	336 KB	Output is correct
13	Correct	3 ms	336 KB	Output is correct
14	Correct	3 ms	336 KB	Output is correct
15	Correct	3 ms	336 KB	Output is correct
16	Correct	3 ms	336 KB	Output is correct
17	Correct	3 ms	336 KB	Output is correct
18	Correct	3 ms	336 KB	Output is correct
19	Correct	3 ms	336 KB	Output is correct
20	Correct	4 ms	336 KB	Output is correct
21	Correct	3 ms	348 KB	Output is correct
22	Correct	3 ms	336 KB	Output is correct
23	Correct	3 ms	344 KB	Output is correct
24	Correct	3 ms	336 KB	Output is correct
25	Correct	3 ms	336 KB	Output is correct
26	Correct	3 ms	336 KB	Output is correct
27	Correct	3 ms	336 KB	Output is correct
28	Correct	3 ms	344 KB	Output is correct
29	Correct	3 ms	336 KB	Output is correct
30	Correct	3 ms	344 KB	Output is correct
31	Correct	3 ms	336 KB	Output is correct
32	Correct	3 ms	348 KB	Output is correct
33	Correct	3 ms	336 KB	Output is correct
34	Correct	3 ms	336 KB	Output is correct
35	Correct	3 ms	348 KB	Output is correct
36	Correct	3 ms	336 KB	Output is correct
37	Correct	3 ms	336 KB	Output is correct
38	Correct	3 ms	336 KB	Output is correct
39	Correct	3 ms	336 KB	Output is correct
40	Correct	3 ms	336 KB	Output is correct