oj.uz

Submission #285763

# Submission time Handle Problem Language Result Execution time Memory
285763 2020-08-29T14:49:40 Z glikcakbn Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 1 ms 384 KB 
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, T; cin >> L >> T;
    int n = (1 << L);

    int A[n];
    for(int i = 0; i < n; ++i)
    {
        char c; cin >> c;
        A[i] = c - '0';
    }

    int B[n]; for(int i = 0; i < n; ++i) B[i] = A[i];
    for(int i = 0; i < L; ++i)
    {
        for(int j = 0; j < n; ++j)
            if(j >> i & 1) B[j] += B[j ^ (1 << i)];
    }

    int C[n]; for(int i = 0; i < n; ++i) C[i] = A[i];
    for(int i = 0; i < L; ++i)
    {
        for(int j = 0; j < n; ++j)
            if(j >> i & 1) C[j ^ (1 << i)] += C[j];
    }

    for(auto i : A) cout << i << ' '; cout << endl;
    for(auto i : B) cout << i << ' '; cout << endl;
    for(auto i : C) cout << i << ' '; cout << endl;

    while(T--)
    {
        int a = 0, b = 0, c = 0;
        int arr[L];
        for(int i = L - 1; i >= 0; --i)
        {
            char t; cin >> t;
            if(t == '0') arr[i] = 0, ++c;
            else if(t == '1') arr[i] = 1, ++b;
            else arr[i] = 2, ++a;
        }

        if(a <= b && a <= c)
        {
            int N = 1 << a;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 2) bt.push_back(1 << i);
                else if(arr[i] == 1) bs |= (1 << i);
            }

            int ans = A[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                ans += A[bs];
            }
            cout << ans << '\n';
        }

        else if(b <= a && b <= c)
        {
            int N = 1 << b;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 1) bt.push_back(1 << i), bs |= (1 << i);
                else if(arr[i] == 2) bs |= (1 << i);
            }

            long long ans = B[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                if(__builtin_parity(i)) ans -= B[bs];
                else ans += B[bs];
            }
            cout << ans << '\n';
        }

        else
        {
            int N = 1 << c;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 0) bt.push_back(1 << i);
                else if(arr[i] == 1) bs |= (1 << i);
            }

            long long ans = C[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                if(__builtin_parity(i)) ans -= C[bs];
                else ans += C[bs];
            }
            cout << ans << '\n';
        }
    }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:35:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |     for(auto i : A) cout << i << ' '; cout << endl;
      |     ^~~
snake_escaping.cpp:35:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   35 |     for(auto i : A) cout << i << ' '; cout << endl;
      |                                       ^~~~
snake_escaping.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |     for(auto i : B) cout << i << ' '; cout << endl;
      |     ^~~
snake_escaping.cpp:36:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |     for(auto i : B) cout << i << ' '; cout << endl;
      |                                       ^~~~
snake_escaping.cpp:37:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   37 |     for(auto i : C) cout << i << ' '; cout << endl;
      |     ^~~
snake_escaping.cpp:37:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   37 |     for(auto i : C) cout << i << ' '; cout << endl;
      |                                       ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -