Submission #876092

#	Time	Username	Problem	Language	Result	Execution time	Memory
876092		green_gold_dog	Monster Game (JOI21_monster)	C++17	0 / 100	123 ms	1320 KiB

monster

#include<bits/stdc++.h>
#include "monster.h"

using namespace std;

random_device rd;
mt19937 rnd(rd());

typedef int ll;

void s(vector<ll>& all) {
        if (all.empty()) {
                return;
        }
        if (true) {
                vector<pair<ll, ll>> now;
                vector<vector<ll>> big(all.size()), sma(all.size());
                for (ll i = 0; i < all.size(); i++) {
                        ll cb = 0;
                        for (ll j = 0; j < all.size(); j++) {
                                if (i != j) {
                                        if (Query(all[i], all[j])) {
                                                sma[i].push_back(j);
                                        } else {
                                                cb++;
                                                big[i].push_back(j);
                                        }
                                }
                        }
                        now.emplace_back(cb, i);
                }
                sort(now.rbegin(), now.rend());
                if (sma[now[1].second][0] == now[0].second) {
                        swap(now[0], now[1]);
                }
                if (big[now[now.size() - 2].second][0] == now.back().second) {
                        swap(now[now.size() - 2], now.back());
                }
                for (ll i = 0; i < all.size(); i++) {
                        all[i] = now[i].second;
                }
                return;
        }
        ll x = rnd() % all.size();
        ll now = all[x];
        cout << now << '\n';
        vector<ll> sm, bi;
        for (ll j = 0; j < all.size(); j++) {
                if (j != x) {
                        if (Query(now, all[j])) {
                                cout << "< " << all[j] << '\n';
                                sm.push_back(all[j]);
                        } else {
                                cout << "> " << all[j] << '\n';
                                bi.push_back(all[j]);
                        }
                }
        }
        s(sm);
        s(bi);
        if (!sm.empty() && !bi.empty()) {
                swap(sm.back(), bi[0]);
        }
        all.clear();
        for (auto i : sm) {
                all.push_back(i);
        }
        all.push_back(now);
        for (auto i : bi) {
                all.push_back(i);
        }
}

vector<ll> Solve(ll n) {
        vector<ll> all;
        for (ll i = 0; i < n; i++) {
                all.push_back(i);
        }
        s(all);
        vector<ll> ans(n);
        for (ll i = 0; i < n; i++) {
                ans[all[i]] = i;
        }
        for (auto i : ans) {
                cout << i << ' ';
        }
        cout << '\n';
        return ans;
}

Compilation message (stderr)

monster.cpp: In function 'void s(std::vector<int>&)':
monster.cpp:18:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |                 for (ll i = 0; i < all.size(); i++) {
      |                                ~~^~~~~~~~~~~~
monster.cpp:20:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |                         for (ll j = 0; j < all.size(); j++) {
      |                                        ~~^~~~~~~~~~~~
monster.cpp:39:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 for (ll i = 0; i < all.size(); i++) {
      |                                ~~^~~~~~~~~~~~
monster.cpp:48:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (ll j = 0; j < all.size(); j++) {
      |                        ~~^~~~~~~~~~~~

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