oj.uz

Submission #864321

# Submission time Handle Problem Language Result Execution time Memory
864321 2023-10-22T11:59:05 Z vjudge1 Monster Game (JOI21_monster) C++17
0 / 100
 7 ms 856 KB 
#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
int N;
vector<int> solve(vector<int>& y, vector<int>& z)
{
    int m = y.size();
    if (m < 9)
    {
    vector<vector<bool> > w(m);
    vector<int> s(m, 0), an(m), eo, enm;
    int i, j;
    for (i = 0; i < m; i++)
    {
        w[i].resize(m);
        for (j = 0; j < m; j++)
        {
            if (j > i)
                w[i][j] = Query(i, j);
            else if (j == i)
                w[i][j] = 0;
            else
                w[i][j] = !w[j][i];
            if (w[i][j])
                s[i]++;
        }
    }
    for (i = 0; i < m; i++)
    {
        if (s[i] == 1)
            eo.push_back(i);
        else if (s[i] == m - 2)
            enm.push_back(i);
        else if (s[i] != 1 && s[i] != m - 2)
            an[i] = s[i];
    }
    if (w[eo[0]][eo[1]])
    {
        an[eo[0]] = 0;
        an[eo[1]] = 1;
    }
    else
    {
        an[eo[0]] = 1;
        an[eo[1]] = 0;
    }
    if (w[enm[0]][enm[1]])
    {
        an[enm[0]] = m - 2;
        an[enm[1]] = m - 1;
    }
    else
    {
        an[enm[0]] = m - 1;
        an[enm[1]] = m - 2;
    }
    return an;
    }
    int i, j, hy, hz;
    vector<int> an(N, -1), s(m, 0), oc(m, 0), ly, lz, ry, rz, le, re;
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < i; j++)
        {
            if (z[i] > z[j] + 1 || z[i] == z[j] - 1)
                s[i]++;
            else
                s[j]++;
        }
    }
    for (i = 0; i < m; i++)
        oc[s[i]]++;
    while (true)
    {
        ly = lz = ry = rz = {};
        mt19937 hh(chrono::steady_clock::now().time_since_epoch().count());
        hy = hh() % m;
        for (i = 0; i < m; i++)
        {
            if (i == hy)
                continue;
            if (Query(y[hy], y[i]))
                ly.push_back(y[i]);
            else
                ry.push_back(y[i]);
        }
        if (oc[ly.size()] == 1)
            break;
    }
    for (i = 0; i < m; i++)
    {
        if (s[i] == ly.size())
        {
            hz = z[i];
            break;
        }
    }
    for (i = 0; i < m; i++)
    {
        if (z[i] == hz)
            continue;
        if (hz > z[i] + 1 || hz == z[i] - 1)
            lz.push_back(z[i]);
        else
            rz.push_back(z[i]);
    }
    if (ly.size())
        le = solve(ly, lz);
    else
        le = an;
    if (ry.size())
        re = solve(ry, rz);
    else
        re = an;
    an[y[hy]] = hz;
    for (i = 0; i < N; i++)
    {
        if (le[i] != -1)
            an[i] = le[i];
        if (re[i] != -1)
            an[i] = re[i];
    }
    return an;
}
vector<int> Solve(int n)
{
    N = n;
    vector<int> y;
    for (int i = 0; i < n; i++)
        y.push_back(i);
    return solve(y, y);
}

Compilation message

monster.cpp: In function 'std::vector<int> solve(std::vector<int>&, std::vector<int>&)':
monster.cpp:92:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if (s[i] == ly.size())
monster.cpp:102:27: warning: 'hz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |         if (hz > z[i] + 1 || hz == z[i] - 1)
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Runtime error 3 ms 600 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Runtime error 3 ms 600 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -