oj.uz

Submission #896352

# Submission time Handle Problem Language Result Execution time Memory
896352 2024-01-01T09:54:30 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 48340 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[1048577];
char queries[1000001][21];
int ansq[1000001];

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))break;
        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 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17580 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17496 KB Output is correct
9 Correct 3 ms 17376 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17580 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17496 KB Output is correct
9 Correct 3 ms 17376 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 242 ms 46312 KB Output is correct
12 Correct 274 ms 46012 KB Output is correct
13 Correct 258 ms 45000 KB Output is correct
14 Correct 256 ms 45140 KB Output is correct
15 Correct 250 ms 46164 KB Output is correct
16 Correct 253 ms 45268 KB Output is correct
17 Correct 257 ms 45380 KB Output is correct
18 Correct 225 ms 47324 KB Output is correct
19 Correct 256 ms 44236 KB Output is correct
20 Correct 243 ms 45808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17580 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17496 KB Output is correct
9 Correct 3 ms 17376 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 242 ms 46312 KB Output is correct
12 Correct 274 ms 46012 KB Output is correct
13 Correct 258 ms 45000 KB Output is correct
14 Correct 256 ms 45140 KB Output is correct
15 Correct 250 ms 46164 KB Output is correct
16 Correct 253 ms 45268 KB Output is correct
17 Correct 257 ms 45380 KB Output is correct
18 Correct 225 ms 47324 KB Output is correct
19 Correct 256 ms 44236 KB Output is correct
20 Correct 243 ms 45808 KB Output is correct
21 Correct 209 ms 46160 KB Output is correct
22 Correct 264 ms 46288 KB Output is correct
23 Correct 288 ms 45372 KB Output is correct
24 Correct 255 ms 45132 KB Output is correct
25 Correct 230 ms 47184 KB Output is correct
26 Correct 311 ms 45808 KB Output is correct
27 Correct 306 ms 45652 KB Output is correct
28 Correct 205 ms 48340 KB Output is correct
29 Correct 270 ms 44244 KB Output is correct
30 Correct 219 ms 46300 KB Output is correct
31 Correct 272 ms 46188 KB Output is correct
32 Correct 245 ms 46160 KB Output is correct
33 Correct 230 ms 45236 KB Output is correct
34 Correct 261 ms 45136 KB Output is correct
35 Correct 296 ms 45640 KB Output is correct
36 Correct 201 ms 44396 KB Output is correct
37 Correct 273 ms 46260 KB Output is correct
38 Correct 255 ms 44368 KB Output is correct
39 Correct 260 ms 45420 KB Output is correct
40 Correct 247 ms 45276 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17580 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17496 KB Output is correct
9 Correct 3 ms 17376 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 307 ms 22056 KB Output is correct
12 Correct 418 ms 21844 KB Output is correct
13 Correct 298 ms 21796 KB Output is correct
14 Correct 350 ms 21800 KB Output is correct
15 Correct 805 ms 22056 KB Output is correct
16 Correct 435 ms 21800 KB Output is correct
17 Correct 461 ms 21796 KB Output is correct
18 Correct 238 ms 22096 KB Output is correct
19 Correct 235 ms 21800 KB Output is correct
20 Correct 395 ms 22052 KB Output is correct
21 Correct 612 ms 22060 KB Output is correct
22 Correct 348 ms 21796 KB Output is correct
23 Correct 265 ms 21848 KB Output is correct
24 Correct 308 ms 21916 KB Output is correct
25 Correct 443 ms 21840 KB Output is correct
26 Correct 156 ms 21844 KB Output is correct
27 Correct 364 ms 22060 KB Output is correct
28 Correct 242 ms 21796 KB Output is correct
29 Correct 271 ms 21800 KB Output is correct
30 Correct 374 ms 21800 KB Output is correct
31 Correct 226 ms 21844 KB Output is correct
32 Correct 461 ms 21844 KB Output is correct
33 Correct 427 ms 21844 KB Output is correct
34 Correct 165 ms 21800 KB Output is correct
35 Correct 442 ms 21800 KB Output is correct
36 Correct 489 ms 21988 KB Output is correct
37 Correct 468 ms 21844 KB Output is correct
38 Correct 479 ms 21796 KB Output is correct
39 Correct 456 ms 21800 KB Output is correct
40 Correct 497 ms 21804 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 3 ms 17500 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Correct 3 ms 17580 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 3 ms 17496 KB Output is correct
9 Correct 3 ms 17376 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 242 ms 46312 KB Output is correct
12 Correct 274 ms 46012 KB Output is correct
13 Correct 258 ms 45000 KB Output is correct
14 Correct 256 ms 45140 KB Output is correct
15 Correct 250 ms 46164 KB Output is correct
16 Correct 253 ms 45268 KB Output is correct
17 Correct 257 ms 45380 KB Output is correct
18 Correct 225 ms 47324 KB Output is correct
19 Correct 256 ms 44236 KB Output is correct
20 Correct 243 ms 45808 KB Output is correct
21 Correct 209 ms 46160 KB Output is correct
22 Correct 264 ms 46288 KB Output is correct
23 Correct 288 ms 45372 KB Output is correct
24 Correct 255 ms 45132 KB Output is correct
25 Correct 230 ms 47184 KB Output is correct
26 Correct 311 ms 45808 KB Output is correct
27 Correct 306 ms 45652 KB Output is correct
28 Correct 205 ms 48340 KB Output is correct
29 Correct 270 ms 44244 KB Output is correct
30 Correct 219 ms 46300 KB Output is correct
31 Correct 272 ms 46188 KB Output is correct
32 Correct 245 ms 46160 KB Output is correct
33 Correct 230 ms 45236 KB Output is correct
34 Correct 261 ms 45136 KB Output is correct
35 Correct 296 ms 45640 KB Output is correct
36 Correct 201 ms 44396 KB Output is correct
37 Correct 273 ms 46260 KB Output is correct
38 Correct 255 ms 44368 KB Output is correct
39 Correct 260 ms 45420 KB Output is correct
40 Correct 247 ms 45276 KB Output is correct
41 Correct 307 ms 22056 KB Output is correct
42 Correct 418 ms 21844 KB Output is correct
43 Correct 298 ms 21796 KB Output is correct
44 Correct 350 ms 21800 KB Output is correct
45 Correct 805 ms 22056 KB Output is correct
46 Correct 435 ms 21800 KB Output is correct
47 Correct 461 ms 21796 KB Output is correct
48 Correct 238 ms 22096 KB Output is correct
49 Correct 235 ms 21800 KB Output is correct
50 Correct 395 ms 22052 KB Output is correct
51 Correct 612 ms 22060 KB Output is correct
52 Correct 348 ms 21796 KB Output is correct
53 Correct 265 ms 21848 KB Output is correct
54 Correct 308 ms 21916 KB Output is correct
55 Correct 443 ms 21840 KB Output is correct
56 Correct 156 ms 21844 KB Output is correct
57 Correct 364 ms 22060 KB Output is correct
58 Correct 242 ms 21796 KB Output is correct
59 Correct 271 ms 21800 KB Output is correct
60 Correct 374 ms 21800 KB Output is correct
61 Correct 226 ms 21844 KB Output is correct
62 Correct 461 ms 21844 KB Output is correct
63 Correct 427 ms 21844 KB Output is correct
64 Correct 165 ms 21800 KB Output is correct
65 Correct 442 ms 21800 KB Output is correct
66 Correct 489 ms 21988 KB Output is correct
67 Correct 468 ms 21844 KB Output is correct
68 Correct 479 ms 21796 KB Output is correct
69 Correct 456 ms 21800 KB Output is correct
70 Correct 497 ms 21804 KB Output is correct
71 Execution timed out 2049 ms 42244 KB Time limit exceeded
72 Halted 0 ms 0 KB -