oj.uz

Submission #964761

# Submission time Handle Problem Language Result Execution time Memory
964761 2024-04-17T13:49:21 Z 12345678 Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 22364 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)&&0)
        {
            for (int i=0; i<l; i++) if (s[i]=='1'||s[i]=='?') tmp+=(1<<i);
        }
        else if (one.size()<=(l/3)||1)
        {
            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';
            }     
        }
    }
}

// 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)&&0)
      |             ~~~~~~~~~~~^~~~~~~
snake_escaping.cpp:34:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         else if (one.size()<=(l/3)||1)
      |                  ~~~~~~~~~~^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 2532 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 2532 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 718 ms 17184 KB Output is correct
12 Correct 410 ms 16936 KB Output is correct
13 Correct 541 ms 15956 KB Output is correct
14 Correct 535 ms 16364 KB Output is correct
15 Correct 477 ms 17064 KB Output is correct
16 Correct 712 ms 16232 KB Output is correct
17 Correct 778 ms 16296 KB Output is correct
18 Correct 278 ms 18052 KB Output is correct
19 Correct 715 ms 15088 KB Output is correct
20 Correct 1410 ms 16972 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 2532 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 718 ms 17184 KB Output is correct
12 Correct 410 ms 16936 KB Output is correct
13 Correct 541 ms 15956 KB Output is correct
14 Correct 535 ms 16364 KB Output is correct
15 Correct 477 ms 17064 KB Output is correct
16 Correct 712 ms 16232 KB Output is correct
17 Correct 778 ms 16296 KB Output is correct
18 Correct 278 ms 18052 KB Output is correct
19 Correct 715 ms 15088 KB Output is correct
20 Correct 1410 ms 16972 KB Output is correct
21 Correct 1191 ms 20200 KB Output is correct
22 Correct 498 ms 20408 KB Output is correct
23 Correct 776 ms 19260 KB Output is correct
24 Correct 700 ms 19188 KB Output is correct
25 Correct 598 ms 21192 KB Output is correct
26 Correct 1144 ms 19640 KB Output is correct
27 Correct 1409 ms 19476 KB Output is correct
28 Correct 334 ms 22364 KB Output is correct
29 Correct 1968 ms 18236 KB Output is correct
30 Execution timed out 2033 ms 7296 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 2532 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Execution timed out 2050 ms 10876 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 2392 KB Output is correct
2 Correct 1 ms 2392 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 2532 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 718 ms 17184 KB Output is correct
12 Correct 410 ms 16936 KB Output is correct
13 Correct 541 ms 15956 KB Output is correct
14 Correct 535 ms 16364 KB Output is correct
15 Correct 477 ms 17064 KB Output is correct
16 Correct 712 ms 16232 KB Output is correct
17 Correct 778 ms 16296 KB Output is correct
18 Correct 278 ms 18052 KB Output is correct
19 Correct 715 ms 15088 KB Output is correct
20 Correct 1410 ms 16972 KB Output is correct
21 Correct 1191 ms 20200 KB Output is correct
22 Correct 498 ms 20408 KB Output is correct
23 Correct 776 ms 19260 KB Output is correct
24 Correct 700 ms 19188 KB Output is correct
25 Correct 598 ms 21192 KB Output is correct
26 Correct 1144 ms 19640 KB Output is correct
27 Correct 1409 ms 19476 KB Output is correct
28 Correct 334 ms 22364 KB Output is correct
29 Correct 1968 ms 18236 KB Output is correct
30 Execution timed out 2033 ms 7296 KB Time limit exceeded
31 Halted 0 ms 0 KB -