oj.uz

Submission #654464

# Submission time Handle Problem Language Result Execution time Memory
654464 2022-10-31T11:19:19 Z Stickfish Monster Game (JOI21_monster) C++17
0 / 100
 38 ms 4220 KB 
#include "monster.h"
#include <algorithm>
#include <random>
using namespace std;

mt19937 rng(177013);

namespace {

bool example_variable;

}  // namespace

const int MAXN = 1001;
int hoh[MAXN][MAXN];

bool qr(int i, int j) {
    if (hoh[i][j] != -1)
        return hoh[i][j];
    bool ans = Query(i, j);
    hoh[i][j] = ans;
    hoh[j][i] = !ans;
    return ans;
}

int trim(vector<int> a, bool type) {
    int m = a.size();
    int cnt = 0;
    vector<int> a0;
    for (int i = 1; i < m; ++i) {
        if (qr(a[0], a[i]) ^ type)
            a0.push_back(a[i]);
    }
    if (a0.empty())
        return a[0];
    return trim(a0, type);
}

int fact(int n) {
    int ans = 1;
    for (int k = 2; k <= n; ++k)
        ans *= k;
    return ans;
}

void solve_bad(vector<int> a, vector<int>& ans, int l) {
    int m = a.size();
    for (int i = 0; i < m; ++i) {
        ans[a[i]] = l;
        for (int j = 0; j < m; ++j) {
            if (i == j)
                continue;
            ans[a[i]] += qr(a[i], a[j]);
        }
    }
    if (m < 4) {
        sort(a.begin(), a.end());
        int pmt = fact(m);
        for (int t = 0; t < pmt; ++t) {
            bool isok = true;
            for (int i = 0; i + 1 < m && isok; ++i) {
                isok &= qr(a[i], a[i + 1]);
                for (int j = i + 2; j < m && isok; ++j)
                    isok &= qr(a[j], a[i]);
            }
            if (isok) {
                for (int i = 0; i < m; ++i)
                    ans[a[i]] = l + i;
                break;
            }
            next_permutation(a.begin(), a.end());
        }
    } else {
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if (ans[a[i]] == ans[a[j]]) {
                    if (qr(a[i], a[j]))
                        swap(a[i], a[j]);
                    if (ans[a[i]] == l + 1)
                        --ans[a[j]];
                    else
                        ++ans[a[i]];
                }
            }
        }
    }
}

void solve_part(vector<int> a, vector<int>& ans, int l) {
    int cnt = 0;
    int m = a.size();
    if (m < 10) {
        solve_bad(a, ans, l);
        return;
    }
    for (int i = 1; i < m; ++i) {
        cnt += qr(a[0], a[i]);
    }
    
    ans[a[0]] = l + cnt;
    vector<int> low;
    vector<int> high;
    for (int i = 1; i < m; ++i) {
        if (qr(a[0], a[i]))
            low.push_back(a[i]);
        else
            high.push_back(a[i]);
    }
    int lowhigh = trim(low, 1);
    int highlow = trim(high, 0);
    low.erase(find(low.begin(), low.end(), lowhigh));
    low.push_back(highlow);
    high.erase(find(high.begin(), high.end(), highlow));
    high.push_back(lowhigh);

    if (4 < cnt && cnt < m - 5) {
        solve_part(low, ans, l);
        solve_part(high, ans, l + cnt + 1);
    } else {
        if (high.size() > low.size()) {
            for (auto& x : a) {
                if (x == high[0]) {
                    swap(x, a[0]);
                    break;
                }
            }
        } else {
            for (auto& x : low) {
                if (x == low[0]) {
                    swap(x, a[0]);
                    break;
                }
            }
        }
        solve_part(a, ans, l);
    }
}

vector<int> Solve(int n) {
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
        hoh[i][j] = -1;
    vector<int> vs(n);
    for (int i = 0; i < n; ++i)
        vs[i] = i;
    shuffle(vs.begin(), vs.end(), rng);
    vector<int> ans(n);
    solve_part(vs, ans, 0);
    return ans;
}

Compilation message

monster.cpp: In function 'int trim(std::vector<int>, bool)':
monster.cpp:28:9: warning: unused variable 'cnt' [-Wunused-variable]
   28 |     int cnt = 0;
      |         ^~~
monster.cpp: At global scope:
monster.cpp:10:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   10 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Incorrect 10 ms 976 KB Wrong Answer [5]
17 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Incorrect 10 ms 976 KB Wrong Answer [5]
17 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 4220 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -