제출 #876127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876127		green_gold_dog	Monster Game (JOI21_monster)	C++17	10 / 100	170 ms	4804 KiB

monster

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

using namespace std;

#define al(a) a.begin(), a.end()

random_device rd;
mt19937 rnd(1);

typedef int ll;

map<pair<ll, ll>, bool> m;

ll N;

bool query(ll a, ll b) {
        return (m.find(make_pair(a, b)) != m.end() ? m[make_pair(a, b)] : (m[make_pair(a, b)] = !(m[make_pair(b, a)] = Query(b, a))));
}

void grnd() {
        ll x = rnd() % N;
        ll y;
        do {
                y = rnd() % N;
        } while (x == y);
        query(x, y);
}

void s(vector<ll>& all) {
        if (all.size() <= 1) {
                return;
        }
        if (all.size() <= 30) {
                vector<pair<ll, ll>> now;
                map<ll, vector<ll>> big, sma;
                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[all[i]].push_back(all[j]);
                                        } else {
                                                cb++;
                                                big[all[i]].push_back(all[j]);
                                        }
                                }
                        }
                        now.emplace_back(cb, all[i]);
                }
                sort(now.rbegin(), now.rend());
                if (sma[now[0].second].empty()) {
                        if (now.size() > 2 && find(al(sma[now[2].second]), now[1].second) != sma[now[2].second].end()) {
                                swap(now[1], now[2]);
                        }
                } else {
                        if (find(al(sma[now[1].second]), now[0].second) != sma[now[1].second].end()) {
                                swap(now[0], now[1]);
                        }
                }
                if (big[now[now.size() - 1].second].empty()) {
                        if (now.size() > 2 && find(al(big[now[now.size() - 3].second]), now[now.size() - 2].second) != big[now[now.size() - 3].second].end()) {
                                swap(now[now.size() - 2], now[now.size() - 3]);
                        }
                } else {
                        if (find(al(big[now[now.size() - 2].second]), now.back().second) != big[now[now.size() - 2].second].end()) {
                                swap(now[now.size() - 2], now.back());
                        }
                }
                for (ll i = 0; i < all.size(); i++) {
                        all[i] = now[i].second;
                }
                return;
        }
        ll x, now;
        vector<ll> sm, bi;
        do {
                x = rnd() % all.size();
                now = all[x];
                sm.clear();
                bi.clear();
                for (ll j = 0; j < all.size(); j++) {
                        if (j != x) {
                                grnd();
                                if (query(now, all[j])) {
                                        sm.push_back(all[j]);
                                } else {
                                        bi.push_back(all[j]);
                                }
                        }
                }
        } while (sm.size() < 6 || bi.size() < 6);
        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) {
        N = 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;
        }
        return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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