oj.uz

Submission #391458

# Submission time Handle Problem Language Result Execution time Memory
391458 2021-04-18T19:18:45 Z iANikzad Snake Escaping (JOI18_snake_escaping) C++11
65 / 100
 2000 ms 10608 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 20;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int sos[1 << 20], rsos[1 << 20];

string s, k;
int l, q;
int a, b, c;

int solve_a() 
{
    int ans = 0, base = 0, mask = 0;
    for(int i = 0;i < l; i++)
    {
        if (k[i] == '?') mask += 1 << i;
        else if (k[i] == '1') base += 1 << i;
    }
  
    for (int i = mask; i; i = mask & (i - 1)) ans += s[i | base] - '0';
    ans += s[base] - '0';
  
    return ans;
}
 
int solve_b() 
{
    int ans = 0, base = 0, mask = 0;
    for(int i = 0;i < l; i++)
    {
        if (k[i] == '0') mask += 1 << i;
        else if (k[i] == '?') base += 1 << i;
    }
  
    for (int i = mask; i; i = mask & (i - 1)) ans += ((b - __builtin_popcount(i)) & 1 ? -1 : 1) * rsos[i | base];
    ans += (b & 1 ? -1 : 1) * rsos[base];
  
    return ans;
}
 
int solve_c() 
{ 
    int ans = 0, base = 0, mask = 0;
    for(int i = 0;i < l; i++)
    {
        if (k[i] == '1') mask += 1 << i;
        else if (k[i] == '?') base += 1 << i;
    }
  
    for (int i = mask; i; i = mask & (i - 1)) ans += ((c - __builtin_popcount(i)) & 1 ? -1 : 1) * sos[i | base];
    ans += (c & 1 ? -1 : 1) * sos[base];
  
    return ans;
}

int main()
{
    FAST;

    cin >> l >> q >> s;

    for(int i = 0; i < (1 << l); i++)
        sos[i] = s[i] - '0', rsos[i] = s[(1 << l) - i - 1] - '0';

    for(int i = 0; i < l; i++) 
        for(int mask = 0; mask < (1 << l); mask++)
            if(mask & (1 << i))
                sos[mask] += sos[mask ^ (1 << i)], rsos[mask] += rsos[mask ^ (1 << i)];

    while(q--)
    {
        cin >> k;
        reverse(all(k));

        a = b = c = 0;
        int ans = 0, base = 0, mask = 0;

        for(int i = 0; i < l; i++)
        {
            if(k[i] == '?') a++;
            if(k[i] == '0') b++;
            if(k[i] == '1') c++;
        }

        if(a < 7) cout << solve_a() << "\n";
        else if(b < 7) cout << solve_b() << "\n";
        else cout << solve_c() << "\n";
    }
  
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:94:13: warning: unused variable 'ans' [-Wunused-variable]
   94 |         int ans = 0, base = 0, mask = 0;
      |             ^~~
snake_escaping.cpp:94:22: warning: unused variable 'base' [-Wunused-variable]
   94 |         int ans = 0, base = 0, mask = 0;
      |                      ^~~~
snake_escaping.cpp:94:32: warning: unused variable 'mask' [-Wunused-variable]
   94 |         int ans = 0, base = 0, mask = 0;
      |                                ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 1894 ms 4912 KB Output is correct
12 Correct 1916 ms 4240 KB Output is correct
13 Correct 1893 ms 3572 KB Output is correct
14 Correct 1896 ms 3644 KB Output is correct
15 Correct 1962 ms 4696 KB Output is correct
16 Correct 1968 ms 3924 KB Output is correct
17 Correct 1954 ms 3936 KB Output is correct
18 Correct 1797 ms 5896 KB Output is correct
19 Correct 1838 ms 2804 KB Output is correct
20 Correct 1883 ms 4560 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 1894 ms 4912 KB Output is correct
12 Correct 1916 ms 4240 KB Output is correct
13 Correct 1893 ms 3572 KB Output is correct
14 Correct 1896 ms 3644 KB Output is correct
15 Correct 1962 ms 4696 KB Output is correct
16 Correct 1968 ms 3924 KB Output is correct
17 Correct 1954 ms 3936 KB Output is correct
18 Correct 1797 ms 5896 KB Output is correct
19 Correct 1838 ms 2804 KB Output is correct
20 Correct 1883 ms 4560 KB Output is correct
21 Correct 1866 ms 5104 KB Output is correct
22 Execution timed out 2041 ms 5284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 139 ms 10504 KB Output is correct
12 Correct 135 ms 10456 KB Output is correct
13 Correct 148 ms 10492 KB Output is correct
14 Correct 167 ms 10400 KB Output is correct
15 Correct 140 ms 10492 KB Output is correct
16 Correct 162 ms 10348 KB Output is correct
17 Correct 170 ms 10468 KB Output is correct
18 Correct 129 ms 10608 KB Output is correct
19 Correct 130 ms 10252 KB Output is correct
20 Correct 135 ms 10500 KB Output is correct
21 Correct 152 ms 10468 KB Output is correct
22 Correct 164 ms 10564 KB Output is correct
23 Correct 137 ms 10384 KB Output is correct
24 Correct 148 ms 10432 KB Output is correct
25 Correct 160 ms 10356 KB Output is correct
26 Correct 124 ms 10360 KB Output is correct
27 Correct 131 ms 10472 KB Output is correct
28 Correct 134 ms 10352 KB Output is correct
29 Correct 137 ms 10352 KB Output is correct
30 Correct 143 ms 10348 KB Output is correct
31 Correct 135 ms 10340 KB Output is correct
32 Correct 168 ms 10468 KB Output is correct
33 Correct 159 ms 10468 KB Output is correct
34 Correct 125 ms 10344 KB Output is correct
35 Correct 153 ms 10492 KB Output is correct
36 Correct 158 ms 10428 KB Output is correct
37 Correct 153 ms 10404 KB Output is correct
38 Correct 153 ms 10468 KB Output is correct
39 Correct 158 ms 10372 KB Output is correct
40 Correct 152 ms 10352 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 1894 ms 4912 KB Output is correct
12 Correct 1916 ms 4240 KB Output is correct
13 Correct 1893 ms 3572 KB Output is correct
14 Correct 1896 ms 3644 KB Output is correct
15 Correct 1962 ms 4696 KB Output is correct
16 Correct 1968 ms 3924 KB Output is correct
17 Correct 1954 ms 3936 KB Output is correct
18 Correct 1797 ms 5896 KB Output is correct
19 Correct 1838 ms 2804 KB Output is correct
20 Correct 1883 ms 4560 KB Output is correct
21 Correct 1866 ms 5104 KB Output is correct
22 Execution timed out 2041 ms 5284 KB Time limit exceeded
23 Halted 0 ms 0 KB -