oj.uz

Submission #150225

# Submission time Handle Problem Language Result Execution time Memory
150225 2019-09-01T07:56:18 Z mit한의대지망생(#3602, TAMREF, imeimi2000, suzy) Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 7 ms 896 KB 
#include "lokahia.h"
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

int FindBase(int n) {
    if (n == 1) return 0;
    if (n <= 25) {
        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(0x525252);
    vector<int> v;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            v.push_back(i * n + j);
        }
    }
    random_shuffle(v.begin(), v.end());
    map<int, set<int>> mp;
    int mxs = 0;
    for (int i = 0; i < 300 - (n - mxs) && i < v.size(); ++i) {
        int a = v[i] / n;
        int b = v[i] % n;
        int ret = CollectRelics(a, b);
        if (ret == -1) continue;
        mp[ret].insert(a);
        mp[ret].insert(b);
        mp[ret].insert(ret);
        mxs = max(mxs, (int)mp[ret].size());
    }
    if (mp.empty()) return -1;
    int mxi = -1;
    set<int> sp;
    for (auto &it : mp) {
        if (it.second.size() == mxs) mxi = it.first, sp = it.second;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (sp.count(i) || CollectRelics(i, mxi) != -1) ++cnt;
    }
    if (cnt >= n / 2) return mxi;
    return -1;
}

Compilation message

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:26:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v.size() >= n / 2) {
                 ~~~~~~~~~^~~~~~~~
lokahia.cpp:42:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < 300 - (n - mxs) && i < v.size(); ++i) {
                                            ~~^~~~~~~~~~
lokahia.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (it.second.size() == mxs) mxi = it.first, sp = it.second;
             ~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Correct : C = 300
2 Incorrect 7 ms 896 KB Wrong
3 Incorrect 6 ms 640 KB Wrong
4 Correct 7 ms 896 KB Correct : C = 300
5 Correct 7 ms 896 KB Correct : C = 101
6 Incorrect 6 ms 896 KB Wrong
7 Correct 5 ms 384 KB Correct : C = 0
8 Correct 6 ms 640 KB Correct : C = 300
9 Correct 7 ms 896 KB Correct : C = 300
10 Correct 7 ms 896 KB Correct : C = 300
11 Correct 7 ms 640 KB Correct : C = 300
12 Correct 7 ms 896 KB Correct : C = 300
13 Correct 7 ms 768 KB Correct : C = 300
14 Correct 6 ms 640 KB Correct : C = 300
15 Correct 7 ms 896 KB Correct : C = 300
16 Correct 6 ms 512 KB Correct : C = 300
17 Correct 7 ms 688 KB Correct : C = 181
18 Correct 7 ms 896 KB Correct : C = 300
19 Correct 7 ms 896 KB Correct : C = 300
20 Incorrect 6 ms 896 KB Wrong
21 Correct 5 ms 640 KB Correct : C = 300
22 Correct 6 ms 512 KB Correct : C = 180
23 Correct 6 ms 512 KB Correct : C = 10
24 Correct 6 ms 640 KB Correct : C = 300
25 Correct 6 ms 816 KB Correct : C = 100
26 Correct 7 ms 896 KB Correct : C = 300
27 Incorrect 6 ms 640 KB Wrong