Submission #1237910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237910		jer033	Monster Game (JOI21_monster)	C++20	0 / 100	2021 ms	4248 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<vector<int>> known_results;

bool ask(int a, int b)
{
    //true if monster a wins
    if (known_results[a][b]!=0)
    {
        if (known_results[a][b] == 1)
            return 1;
        return 0;
    }
    bool ans = Query(a, b);
    if (ans)
    {
        known_results[a][b] = 1;
        known_results[b][a] = -1;
    }
    else
    {
        known_results[a][b] = -1;
        known_results[b][a] = 1;
    }
    return ans;
}

std::vector<int> Solve(int N) {
    known_results = vector<vector<int>> (1005, vector<int> (1005, 0));
    vector<int> temporary_results(1005, 0);
    for (int i=1; i<N; i++)
    {
        vector<pii> curr;
        for (int j=0; j<i; j++)
            curr.push_back({temporary_results[j], j});
        sort(curr.begin(), curr.end());
        int range_lo = curr[0].first;
        int range_hi = curr[i-1].first;
        while ((range_hi - range_lo) > 10)
        {
            int range_mid = (range_lo + range_hi)/2;
            int real_range_mid = -1;
            int diff = N+5;
            int ind = -1;
            for (int j=0; j<i; j++)
                if (abs(curr[j].first - range_mid) < diff)
                {
                    real_range_mid = curr[j].first;
                    diff = abs(curr[j].first - range_mid);
                    ind = curr[j].second;
                }
            bool x = ask(i, ind);
            if (x)
            {
                for (int j=0; j<i; j++)
                    if (((curr[j].first + 5) <= real_range_mid) and (known_results[i][curr[j].second] == 0))
                    {
                        known_results[i][curr[j].second] = 1;
                        known_results[curr[j].second][i] = -1;
                    }
                range_lo = real_range_mid - 5;
            }
            else
            {
                for (int j=0; j<i; j++)
                    if (((curr[j].first - 5) >= real_range_mid) and (known_results[i][curr[j].second] == 0))
                    {
                        known_results[i][curr[j].second] = -1;
                        known_results[curr[j].second][i] = 1;
                    }
                range_hi = real_range_mid + 5;
            }
        }
        for (int j=0; j<i; j++)
        {
            if (ask(i, j))
                temporary_results[i]++;
            else
                temporary_results[j]++;
        }
    }

    vector<pii> curr;
    for (int j=0; j<N; j++)
        curr.push_back({temporary_results[j], j});
    sort(curr.begin(), curr.end());
    int lo_a = curr[0].second;
    int lo_b = curr[1].second;
    if (ask(lo_b, lo_a))
        swap(lo_a, lo_b);
    int hi_a = curr[N-2].second;
    int hi_b = curr[N-1].second;
    if (ask(hi_b, hi_a))
        swap(hi_a, hi_b);
    vector<int> answer = {lo_a, lo_b};
    for (int j=2; j<(N-2); j++)
        answer.push_back(curr[j].second);
    answer.push_back(hi_a);
    answer.push_back(hi_b);
    return answer;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75