oj.uz

Submission #939272

# Submission time Handle Problem Language Result Execution time Memory
939272 2024-03-06T07:58:28 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 16200 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

#define int ll

struct test
{
    void solve(int testcase)
    {
        boost();

        int n, q;
        cin >> n >> q;
        int mxBit = n;
        n = 1 << n;
        vector<int> cost(n);
        for (int i = 0; i < n; ++i)
        {
            char x;
            cin >> x;
            cost[i] = x - '0';
        }
        for (int i = 0; i < q; ++i)
        {
            int mask0 = 0, mask1 = 0;
            string T;
            cin >> T;
            reverse(all(T));
            for (int p = 0; p < mxBit; ++p)
            {
                char x = T[p];
                if (x == '0')
                    mask0 += (1 << p);
                if (x == '1')
                    mask1 += (1 << p);
            }
            int res = 0;
            for (int i = 0; i < n; ++i)
                if ((i & mask1) == mask1 and ((~i) & mask0) == mask0)
                    res += cost[i];

            cout << res << '\n';
        }
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message

snake_escaping.cpp:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main()
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 624 ms 15444 KB Output is correct
12 Correct 762 ms 14968 KB Output is correct
13 Correct 907 ms 13920 KB Output is correct
14 Correct 816 ms 14432 KB Output is correct
15 Correct 987 ms 15192 KB Output is correct
16 Correct 881 ms 14284 KB Output is correct
17 Correct 861 ms 14416 KB Output is correct
18 Correct 814 ms 16200 KB Output is correct
19 Correct 621 ms 13168 KB Output is correct
20 Correct 642 ms 14736 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 624 ms 15444 KB Output is correct
12 Correct 762 ms 14968 KB Output is correct
13 Correct 907 ms 13920 KB Output is correct
14 Correct 816 ms 14432 KB Output is correct
15 Correct 987 ms 15192 KB Output is correct
16 Correct 881 ms 14284 KB Output is correct
17 Correct 861 ms 14416 KB Output is correct
18 Correct 814 ms 16200 KB Output is correct
19 Correct 621 ms 13168 KB Output is correct
20 Correct 642 ms 14736 KB Output is correct
21 Execution timed out 2036 ms 12272 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Execution timed out 2048 ms 9980 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 624 ms 15444 KB Output is correct
12 Correct 762 ms 14968 KB Output is correct
13 Correct 907 ms 13920 KB Output is correct
14 Correct 816 ms 14432 KB Output is correct
15 Correct 987 ms 15192 KB Output is correct
16 Correct 881 ms 14284 KB Output is correct
17 Correct 861 ms 14416 KB Output is correct
18 Correct 814 ms 16200 KB Output is correct
19 Correct 621 ms 13168 KB Output is correct
20 Correct 642 ms 14736 KB Output is correct
21 Execution timed out 2036 ms 12272 KB Time limit exceeded
22 Halted 0 ms 0 KB -