oj.uz

Submission #964768

# Submission time Handle Problem Language Result Execution time Memory
964768 2024-04-17T14:05:20 Z 12345678 Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 17280 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=(1<<20)+5;

int l, q, sub[nx], super[nx];
char c;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>l>>q;
    for (int i=0; i<(1<<l); i++) cin>>c, sub[i]=super[i]=c-'0';
    for (int i=0; i<l; i++) for (int j=0; j<(1<<l); j++) if (j&(1<<i)) sub[j]+=sub[j^(1<<i)];
    for (int i=0; i<l; i++) for (int j=(1<<l)-1; j>=0; j--) if (!(j&(1<<i))) super[j]+=super[j^(1<<i)];
    while (q--)
    {
        cin>>s;
        reverse(s.begin(), s.end());
        int tmp=0;
        vector<int> zero, one, qrs;
        for (int i=0; i<l; i++)
        {
            if (s[i]=='0') zero.push_back(i);
            if (s[i]=='1') one.push_back(i);
            if (s[i]=='?') qrs.push_back(i);
        }
        if (zero.size()<=(l/3)||1)
        {
            for (int i=0; i<l; i++) if (s[i]=='1') tmp+=(1<<i);
            if (zero.empty()) cout<<super[tmp]<<'\n';
            else
            {
                int sz=zero.size(), res=0;
                for (int i=0; i<(1<<sz); i++)
                {
                    int vl=tmp;
                    for (int j=0; j<sz; j++) if ((i&(1<<j))) vl+=(1<<zero[j]);
                    //cout<<"debug "<<i<<' '<<vl<<'\n';
                    if ((__builtin_popcount(i)%2)==0) res+=super[vl];
                    else res-=super[vl];
                }
                cout<<res<<'\n';
            }
        }
        else if (one.size()<=(l/3))
        {
            for (int i=0; i<l; i++) if (s[i]=='?') tmp+=(1<<i);
            if (one.empty()) cout<<sub[tmp]<<'\n';
            else
            {
                int sz=one.size(), res=0;
                for (int i=0; i<(1<<sz); i++)
                {
                    int vl=tmp;
                    for (int j=0; j<sz; j++) if (i&(1<<j)) vl+=(1<<one[j]);
                    if ((sz-__builtin_popcount(i))%2==0) res+=sub[vl];
                    else res-=sub[vl];
                }
                cout<<res<<'\n';
            }     
        }
        else
        {

        }
    }
}

// 00011???

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if (zero.size()<=(l/3)||1)
      |             ~~~~~~~~~~~^~~~~~~
snake_escaping.cpp:48:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         else if (one.size()<=(l/3))
      |                  ~~~~~~~~~~^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2468 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2468 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 420 ms 14936 KB Output is correct
12 Correct 1336 ms 14468 KB Output is correct
13 Correct 731 ms 13680 KB Output is correct
14 Correct 569 ms 13940 KB Output is correct
15 Correct 453 ms 14928 KB Output is correct
16 Correct 553 ms 13976 KB Output is correct
17 Correct 699 ms 13944 KB Output is correct
18 Correct 308 ms 15812 KB Output is correct
19 Correct 686 ms 13156 KB Output is correct
20 Correct 422 ms 14476 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2468 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 420 ms 14936 KB Output is correct
12 Correct 1336 ms 14468 KB Output is correct
13 Correct 731 ms 13680 KB Output is correct
14 Correct 569 ms 13940 KB Output is correct
15 Correct 453 ms 14928 KB Output is correct
16 Correct 553 ms 13976 KB Output is correct
17 Correct 699 ms 13944 KB Output is correct
18 Correct 308 ms 15812 KB Output is correct
19 Correct 686 ms 13156 KB Output is correct
20 Correct 422 ms 14476 KB Output is correct
21 Correct 486 ms 17280 KB Output is correct
22 Execution timed out 2051 ms 7520 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2468 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 75 ms 11040 KB Output is correct
12 Execution timed out 2048 ms 10156 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2468 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 420 ms 14936 KB Output is correct
12 Correct 1336 ms 14468 KB Output is correct
13 Correct 731 ms 13680 KB Output is correct
14 Correct 569 ms 13940 KB Output is correct
15 Correct 453 ms 14928 KB Output is correct
16 Correct 553 ms 13976 KB Output is correct
17 Correct 699 ms 13944 KB Output is correct
18 Correct 308 ms 15812 KB Output is correct
19 Correct 686 ms 13156 KB Output is correct
20 Correct 422 ms 14476 KB Output is correct
21 Correct 486 ms 17280 KB Output is correct
22 Execution timed out 2051 ms 7520 KB Time limit exceeded
23 Halted 0 ms 0 KB -