Submission #150647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
150647	2019-09-01T08:46:24 Z	mit한의대지망생(#3602, TAMREF, imeimi2000, suzy)	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	7 ms	640 KB

lokahia

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

using namespace std;

int FindBase(int n) {
    if (n <= 3) return 0;
    int ord[201];
    int out[201];
    int same[201];
    int same1[201] = {};
    for (int i = 0; i < n; ++i) ord[i] = i;
    srand(0x52525522);
    random_shuffle(ord, ord + n);
    vector<int> L;
    L.push_back(0);
    same[0] = 1;
    out[0] = ord[0];
    int sum = 1, c = -1;
    for (int i = 1; i < n; ++i) {
        int ret = CollectRelics(ord[L.back()], ord[i]);
        if (ret != -1) {
            out[L.back()] = out[i] = ret;
            ++sum;
            same[i] = 1;
        }
        else {
            out[i] = ord[i];
            same[i] = 0;
            c = i;
            --sum;
        }
        if (sum == 0) {
            ++i;
            if (i < n) same[i] = 1;
            if (i < n) out[i] = ord[i];
            if (i < n) L.push_back(i);
            ++sum;
        }
    }
    vector<int> C;
    int del = sum;
    for (int i = 0; i < (int)L.size() - 1; ++i) {
        int a = L[i], b = L[i + 1];
        int ret = CollectRelics(ord[a], ord[L.back()]);
        if (ret != -1) {
            out[a] = out[L.back()] = ret;
            for (int j = a; j < b; ++j) {
                if (same1[j] = same[j]) continue;
                c = j;
            }
            continue;
        }
        for (int j = a; j < b; ++j) {
            same1[j] = 0;
            if (same[j]) {
                continue;
            }
            int ret = CollectRelics(ord[L.back()], ord[j]);
            if (ret != -1) {
                same1[j] = 1;
                out[L.back()] = out[j] = ret;
            }
            else {
                c = j;
                if ((del -= 2) < -1) break;
            }
        }
        if (del < -1) break;
    }
    if (sum > 1 && del < -1) return -1;
    if (del > -2) return out[L.back()];
    if (c == -1) return -1;
    del = -sum;
    for (int i = 0; i < (int)L.size() - 1; ++i) {
        int a = L[i], b = L[i + 1];
        int ret = -1;
        if (same1[a] == 0) {
            if (a == c) ret = out[c];
            else ret = CollectRelics(ord[a], ord[c]);
        }
        if (ret != -1) {
            out[a] = out[c] = ret;
            continue;
        }
        for (int j = a; j < b; ++j) {
            if (same[j] || same1[j]) {
                continue;
            }
            int ret;
            if (c == j) ret = out[c];
            else ret = CollectRelics(ord[c], ord[j]);
            if (ret != -1) {
                out[c] = out[j] = ret;
            }
            else if ((del -= 2) < -1) break;
        }
        if (del < -1) break;
    }
    for (int i = L.back(); i < n; ++i) {
        if (same[i]) continue;
        int ret;
        if (c == i) ret = out[c];
        else CollectRelics(ord[c], ord[i]);
        if (ret != -1) {
            out[c] = out[i] = ret;
        }
        else if ((del -= 2) < -1) break;
    }
    if (del < -1) return -1;
    return out[c];
}

Compilation message

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:53:30: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
                 if (same1[j] = same[j]) continue;
                     ~~~~~~~~~^~~~~~~~~
lokahia.cpp:109:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (ret != -1) {
         ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	640 KB	Correct : C = 198
2	Correct	6 ms	384 KB	Correct : C = 0
3	Incorrect	6 ms	512 KB	Wrong
4	Correct	6 ms	640 KB	Correct : C = 204
5	Incorrect	7 ms	640 KB	Wrong
6	Correct	6 ms	640 KB	Correct : C = 138
7	Correct	6 ms	512 KB	Correct : C = 119
8	Correct	6 ms	640 KB	Correct : C = 107
9	Correct	7 ms	640 KB	Correct : C = 294
10	Correct	6 ms	512 KB	Correct : C = 118
11	Incorrect	6 ms	512 KB	Wrong
12	Correct	6 ms	640 KB	Correct : C = 131
13	Incorrect	5 ms	512 KB	Wrong
14	Correct	6 ms	640 KB	Correct : C = 105
15	Correct	6 ms	640 KB	Correct : C = 291
16	Correct	6 ms	512 KB	Correct : C = 4
17	Correct	6 ms	512 KB	Correct : C = 131
18	Correct	6 ms	512 KB	Correct : C = 156
19	Correct	6 ms	640 KB	Correct : C = 199
20	Correct	6 ms	640 KB	Correct : C = 213
21	Correct	6 ms	512 KB	Correct : C = 65
22	Correct	7 ms	640 KB	Correct : C = 200
23	Correct	6 ms	640 KB	Correct : C = 218
24	Correct	6 ms	512 KB	Correct : C = 119
25	Correct	5 ms	512 KB	Correct : C = 67
26	Correct	6 ms	512 KB	Correct : C = 122
27	Correct	6 ms	640 KB	Correct : C = 198