Submission #150138

#	Time	Username	Problem	Language	Result	Execution time	Memory
150138		mit한의대지망생 (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	8 ms	688 KiB

lokahia

#include "lokahia.h"
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>

using namespace std;

int FindBase(int n) {
    if (n == 1) return 0;
    if (n <= 2) {
        map<int, vector<int>> mp;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int ret = CollectRelics(i, j);
                if (ret == -1) continue;
                mp[ret].push_back(i);
                mp[ret].push_back(j);
            }
        }
        for (auto it : mp) {
            vector<int> v = it.second;
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            if (v.size() >= n / 2) {
                return it.first;
            }
        }
        return -1;
    }
    srand(0x5252);
    map<int, vector<int>> mp;
    for (int i = 0; i < 300 - n; ++i) {
        int a, b;
        do {
            a = rand() % n, b = rand() % n;
        } while (a == b);
        int ret = CollectRelics(a, b);
        if (ret == -1) continue;
        mp[ret].push_back(a);
        mp[ret].push_back(b);
    }
    if (mp.empty()) return -1;
    int mxi = -1, mxv = -1;
    for (auto &it : mp) {
        vector<int> &v = it.second;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        if ((int)v.size() > mxv) mxi = it.first, mxv = (int)v.size();
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (i == mxi || CollectRelics(i, mxi) != -1) ++cnt;
    }
    if (cnt >= n / 2) return mxi;
    return -1;
}

Compilation message (stderr)

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:25:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v.size() >= n / 2) {
                 ~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 100