oj.uz

Submission #889358

# Submission time Handle Problem Language Result Execution time Memory
889358 2023-12-19T12:24:08 Z hariaakas646 Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 53540 KB 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
 
using namespace std;
 
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;
 
 
void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}
 
void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int main() {
    // usaco();
    fastio();
    int l, q;
    cin >> l >> q;
    string str;
    cin >> str;
 
    vi mv(1<<l);
 
    frange(i, 1<<l) {
        mv[i] = str[i] - '0';
    }
 
    vi po3(l+1);
    po3[0] = 1;
    forr(i, 1, l+1) po3[i] = po3[i-1] * 3;
 
    vector<string> quer(q);
 
    frange(i, q) {
        cin >> quer[i];
        reverse(all(quer[i]));
    }
    int v1 = min(l, 6);
 
    vi pos(1<<l);
    frange(i, 1<<l) {
        frange(j, v1) {
            pos[i] += (i&(1<<j));
        }
    }
 
    
    vi out(q);
    frange(i, 1<<v1) {
        vi val;
        // cout << i << "\n";
        frange(j, 1<<l) {
            if(pos[j] == i) {val.pb(mv[j]);}
        }
 
        
        // for(auto e : val) cout << e << " ";
        // cout << "\n";
 
        int v = 1;
        frange(i, l-v1) v *= 3;
 
        vi tot(v);
 
        frange(i, v) {
            int li=0;
            int r = 0;
            int x = 0;
            int k = i;
            bool done = false;
            frange(j, l-v1) {
                if(k % 3 == 1) {
                    x += po3[j];
                    li += po3[j];
                    r += po3[j];
                }
                else if(k % 3 == 2) {
                    x += po3[j] * 2;
                    if(!done)
                        {r += po3[j]; done = true;}
                    else {
                        li += po3[j] * 2;;
                        r += po3[j] * 2;
                    }
                }
                k /= 3;
            }
            k = i;
            if(!done) {
                int x2 = 0;
                frange(j, l-v1) {
                    if(k % 3 == 1) {
                        x2 += (1<<j);
                    }
                    k /= 3;
                }
                tot[x] = val[x2];
            }
            else {
                // cout << x << " " << li << " " << r << "\n";
                tot[x] = tot[li] + tot[r];
            }
        }
 
        frange(k, q) {
            auto& st = quer[k];
            bool done = true;
            frange(j, v1) {
                if(st[j] == '?') continue;
                int dig = st[j] - '0';
                if(dig != (bool)(i&(1<<j))) {
                    done = false;
                    break;
                }
            }
            if(done) {
                int num = 0;
                frange(j, l-v1) {
                    if(st[v1+j] == '1') num += po3[j];
                    else if(st[v1+j] == '?') num += 2*po3[j];
                }
                // cout << k << " " << num << "\n";
                out[k] += tot[num];
            }
        }
    }
 
    frange(i, q) cout << out[i] << "\n";
}

Compilation message

snake_escaping.cpp: In function 'void usaco()':
snake_escaping.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1249 ms 39764 KB Output is correct
12 Correct 1470 ms 50012 KB Output is correct
13 Correct 1000 ms 49236 KB Output is correct
14 Correct 1142 ms 49616 KB Output is correct
15 Correct 1838 ms 50264 KB Output is correct
16 Correct 1360 ms 49408 KB Output is correct
17 Correct 1360 ms 49500 KB Output is correct
18 Correct 691 ms 51288 KB Output is correct
19 Correct 757 ms 48328 KB Output is correct
20 Correct 1463 ms 50004 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1249 ms 39764 KB Output is correct
12 Correct 1470 ms 50012 KB Output is correct
13 Correct 1000 ms 49236 KB Output is correct
14 Correct 1142 ms 49616 KB Output is correct
15 Correct 1838 ms 50264 KB Output is correct
16 Correct 1360 ms 49408 KB Output is correct
17 Correct 1360 ms 49500 KB Output is correct
18 Correct 691 ms 51288 KB Output is correct
19 Correct 757 ms 48328 KB Output is correct
20 Correct 1463 ms 50004 KB Output is correct
21 Correct 1514 ms 53288 KB Output is correct
22 Correct 1595 ms 53540 KB Output is correct
23 Correct 1138 ms 52516 KB Output is correct
24 Correct 1271 ms 52260 KB Output is correct
25 Execution timed out 2027 ms 52512 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1249 ms 39764 KB Output is correct
12 Correct 1470 ms 50012 KB Output is correct
13 Correct 1000 ms 49236 KB Output is correct
14 Correct 1142 ms 49616 KB Output is correct
15 Correct 1838 ms 50264 KB Output is correct
16 Correct 1360 ms 49408 KB Output is correct
17 Correct 1360 ms 49500 KB Output is correct
18 Correct 691 ms 51288 KB Output is correct
19 Correct 757 ms 48328 KB Output is correct
20 Correct 1463 ms 50004 KB Output is correct
21 Correct 1514 ms 53288 KB Output is correct
22 Correct 1595 ms 53540 KB Output is correct
23 Correct 1138 ms 52516 KB Output is correct
24 Correct 1271 ms 52260 KB Output is correct
25 Execution timed out 2027 ms 52512 KB Time limit exceeded
26 Halted 0 ms 0 KB -