oj.uz

Submission #896328

# Submission time Handle Problem Language Result Execution time Memory
896328 2024-01-01T09:28:29 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 731 ms 55888 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<ll> point;
#define X real()
#define Y imag()
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const ll INF = 1e17;
const ll sqrtn = 440;
const ll modulo = 1e9+7;
const ll siz = 262144;
const ll hashp = 923981238;
const ll hashm = 932439994;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll

int memo[1594323];
char str[1048576];
char queries[1000000][20];
int ansq[1000000];

int get(char *s,int i){
    if(memo[i]!=-1)return memo[i];
    int p = 1;
    for(int x=0;x<13;x++) {
        if (s[x] == '?') {
            s[x] = '0';
            int ans = get(s, i + p);
            s[x] = '1';
            ans += get(s, i + 2 * p);
            s[x] = '?';
            return memo[i] = ans;
        }
        p*=3;
    }
}

int getidx(const char *s){
    int p = 1;
    int ans = 0;
    for(int a=0;a<13;a++){
        if(s[a]=='0')ans+=p;
        else if(s[a]=='1')ans+=p*2;
        p*=3;
    }
    return ans;
}

inline bool match(string a,const char *b){
    for(int i=0;i<7;i++)if(b[i]!='?' and a[i]!=b[i])return false;
    return true;
}

void solve() {
    int l,q;
    cin >> l >> q;
    for(int i=0;i<(1<<l);i++)cin >> str[i];
    for(int i=0;i<(1<<l);i++)str[i]-='0';
    for(int i=1;i<=q;i++){
        string s;cin>>s;
        for(int x=0;x<20-l;x++)s.insert(s.begin(),'0');
        for(int x=0;x<20;x++)queries[i][x] = s[x];
    }
    for(int modifier=0;modifier<(1<<7);modifier++){
        if(modifier<<13 > 1<<l)continue;
        string m = bitset<7>(modifier).to_string();
        for(int&i:memo)i=-1;
        for(int i=0;i<(1<<13);i++)memo[getidx(bitset<13>(i).to_string().c_str())]=str[(modifier<<13)+i];
        for(int i=1;i<=q;i++){
            if(!match(m,queries[i]))continue;
            ansq[i]+=get(queries[i]+7,getidx(queries[i]+7));
        }
    }
    for(int i=1;i<=q;i++)cout<<ansq[i]<<'\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("cses.fi.txt","r",stdin);
//    freopen(".out","w",stdout);
//    int t;
//    cin >> t;
//    while(t--)
    solve();
}

Compilation message

snake_escaping.cpp: In function 'll get(char*, ll)':
snake_escaping.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 4 ms 16476 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 5 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16476 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 240 ms 45136 KB Output is correct
12 Correct 292 ms 55888 KB Output is correct
13 Incorrect 279 ms 55120 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 4 ms 16476 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 5 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16476 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 240 ms 45136 KB Output is correct
12 Correct 292 ms 55888 KB Output is correct
13 Incorrect 279 ms 55120 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 4 ms 16476 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 5 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16476 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 364 ms 21072 KB Output is correct
12 Correct 448 ms 21084 KB Output is correct
13 Correct 315 ms 20824 KB Output is correct
14 Correct 387 ms 20828 KB Output is correct
15 Correct 731 ms 21076 KB Output is correct
16 Correct 484 ms 20824 KB Output is correct
17 Correct 494 ms 20824 KB Output is correct
18 Correct 268 ms 21072 KB Output is correct
19 Correct 255 ms 21072 KB Output is correct
20 Correct 395 ms 21076 KB Output is correct
21 Correct 614 ms 21328 KB Output is correct
22 Correct 380 ms 21012 KB Output is correct
23 Correct 271 ms 20824 KB Output is correct
24 Correct 374 ms 20840 KB Output is correct
25 Correct 471 ms 21076 KB Output is correct
26 Correct 217 ms 20896 KB Output is correct
27 Correct 411 ms 21076 KB Output is correct
28 Correct 282 ms 20828 KB Output is correct
29 Correct 311 ms 20824 KB Output is correct
30 Correct 392 ms 20828 KB Output is correct
31 Correct 295 ms 20828 KB Output is correct
32 Correct 464 ms 20836 KB Output is correct
33 Correct 558 ms 20828 KB Output is correct
34 Correct 200 ms 20828 KB Output is correct
35 Correct 489 ms 20824 KB Output is correct
36 Correct 443 ms 20824 KB Output is correct
37 Correct 472 ms 20824 KB Output is correct
38 Correct 451 ms 20824 KB Output is correct
39 Correct 454 ms 20820 KB Output is correct
40 Correct 504 ms 20828 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 4 ms 16476 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 5 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16476 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 240 ms 45136 KB Output is correct
12 Correct 292 ms 55888 KB Output is correct
13 Incorrect 279 ms 55120 KB Output isn't correct
14 Halted 0 ms 0 KB -