oj.uz

답안 #896351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896351 2024-01-01T09:53:23 Z Unforgettablepl Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 48104 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17496 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 17500 KB Output is correct
6 Correct 3 ms 17752 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 3 ms 17500 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17496 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 17500 KB Output is correct
6 Correct 3 ms 17752 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 3 ms 17500 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 241 ms 46160 KB Output is correct
12 Correct 292 ms 45908 KB Output is correct
13 Correct 293 ms 45140 KB Output is correct
14 Correct 274 ms 45136 KB Output is correct
15 Correct 265 ms 46420 KB Output is correct
16 Correct 273 ms 45536 KB Output is correct
17 Correct 283 ms 45464 KB Output is correct
18 Correct 242 ms 47188 KB Output is correct
19 Correct 282 ms 44240 KB Output is correct
20 Correct 243 ms 45788 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17496 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 17500 KB Output is correct
6 Correct 3 ms 17752 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 3 ms 17500 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 241 ms 46160 KB Output is correct
12 Correct 292 ms 45908 KB Output is correct
13 Correct 293 ms 45140 KB Output is correct
14 Correct 274 ms 45136 KB Output is correct
15 Correct 265 ms 46420 KB Output is correct
16 Correct 273 ms 45536 KB Output is correct
17 Correct 283 ms 45464 KB Output is correct
18 Correct 242 ms 47188 KB Output is correct
19 Correct 282 ms 44240 KB Output is correct
20 Correct 243 ms 45788 KB Output is correct
21 Correct 224 ms 46160 KB Output is correct
22 Correct 278 ms 46452 KB Output is correct
23 Correct 296 ms 45360 KB Output is correct
24 Correct 277 ms 45140 KB Output is correct
25 Correct 256 ms 47180 KB Output is correct
26 Correct 286 ms 45652 KB Output is correct
27 Correct 296 ms 45780 KB Output is correct
28 Correct 236 ms 48104 KB Output is correct
29 Correct 269 ms 44244 KB Output is correct
30 Correct 235 ms 46632 KB Output is correct
31 Correct 276 ms 46156 KB Output is correct
32 Correct 277 ms 46280 KB Output is correct
33 Correct 260 ms 45000 KB Output is correct
34 Correct 292 ms 45236 KB Output is correct
35 Correct 303 ms 45784 KB Output is correct
36 Correct 219 ms 44112 KB Output is correct
37 Correct 273 ms 46296 KB Output is correct
38 Correct 275 ms 44248 KB Output is correct
39 Correct 269 ms 45396 KB Output is correct
40 Correct 269 ms 45144 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17496 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 17500 KB Output is correct
6 Correct 3 ms 17752 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 3 ms 17500 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 355 ms 22052 KB Output is correct
12 Correct 445 ms 22056 KB Output is correct
13 Correct 318 ms 21804 KB Output is correct
14 Correct 409 ms 21840 KB Output is correct
15 Correct 768 ms 22056 KB Output is correct
16 Correct 477 ms 21800 KB Output is correct
17 Correct 493 ms 21800 KB Output is correct
18 Correct 276 ms 22100 KB Output is correct
19 Correct 266 ms 21800 KB Output is correct
20 Correct 409 ms 22052 KB Output is correct
21 Correct 621 ms 22052 KB Output is correct
22 Correct 383 ms 21804 KB Output is correct
23 Correct 289 ms 21812 KB Output is correct
24 Correct 343 ms 21928 KB Output is correct
25 Correct 496 ms 21804 KB Output is correct
26 Correct 185 ms 21840 KB Output is correct
27 Correct 405 ms 21840 KB Output is correct
28 Correct 250 ms 21804 KB Output is correct
29 Correct 326 ms 21804 KB Output is correct
30 Correct 346 ms 21796 KB Output is correct
31 Correct 272 ms 21800 KB Output is correct
32 Correct 485 ms 21840 KB Output is correct
33 Correct 435 ms 21844 KB Output is correct
34 Correct 190 ms 21812 KB Output is correct
35 Correct 448 ms 21844 KB Output is correct
36 Correct 455 ms 21800 KB Output is correct
37 Correct 450 ms 21796 KB Output is correct
38 Correct 447 ms 21844 KB Output is correct
39 Correct 460 ms 21796 KB Output is correct
40 Correct 463 ms 21804 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 17496 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 17500 KB Output is correct
6 Correct 3 ms 17752 KB Output is correct
7 Correct 3 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 3 ms 17500 KB Output is correct
10 Correct 3 ms 17500 KB Output is correct
11 Correct 241 ms 46160 KB Output is correct
12 Correct 292 ms 45908 KB Output is correct
13 Correct 293 ms 45140 KB Output is correct
14 Correct 274 ms 45136 KB Output is correct
15 Correct 265 ms 46420 KB Output is correct
16 Correct 273 ms 45536 KB Output is correct
17 Correct 283 ms 45464 KB Output is correct
18 Correct 242 ms 47188 KB Output is correct
19 Correct 282 ms 44240 KB Output is correct
20 Correct 243 ms 45788 KB Output is correct
21 Correct 224 ms 46160 KB Output is correct
22 Correct 278 ms 46452 KB Output is correct
23 Correct 296 ms 45360 KB Output is correct
24 Correct 277 ms 45140 KB Output is correct
25 Correct 256 ms 47180 KB Output is correct
26 Correct 286 ms 45652 KB Output is correct
27 Correct 296 ms 45780 KB Output is correct
28 Correct 236 ms 48104 KB Output is correct
29 Correct 269 ms 44244 KB Output is correct
30 Correct 235 ms 46632 KB Output is correct
31 Correct 276 ms 46156 KB Output is correct
32 Correct 277 ms 46280 KB Output is correct
33 Correct 260 ms 45000 KB Output is correct
34 Correct 292 ms 45236 KB Output is correct
35 Correct 303 ms 45784 KB Output is correct
36 Correct 219 ms 44112 KB Output is correct
37 Correct 273 ms 46296 KB Output is correct
38 Correct 275 ms 44248 KB Output is correct
39 Correct 269 ms 45396 KB Output is correct
40 Correct 269 ms 45144 KB Output is correct
41 Correct 355 ms 22052 KB Output is correct
42 Correct 445 ms 22056 KB Output is correct
43 Correct 318 ms 21804 KB Output is correct
44 Correct 409 ms 21840 KB Output is correct
45 Correct 768 ms 22056 KB Output is correct
46 Correct 477 ms 21800 KB Output is correct
47 Correct 493 ms 21800 KB Output is correct
48 Correct 276 ms 22100 KB Output is correct
49 Correct 266 ms 21800 KB Output is correct
50 Correct 409 ms 22052 KB Output is correct
51 Correct 621 ms 22052 KB Output is correct
52 Correct 383 ms 21804 KB Output is correct
53 Correct 289 ms 21812 KB Output is correct
54 Correct 343 ms 21928 KB Output is correct
55 Correct 496 ms 21804 KB Output is correct
56 Correct 185 ms 21840 KB Output is correct
57 Correct 405 ms 21840 KB Output is correct
58 Correct 250 ms 21804 KB Output is correct
59 Correct 326 ms 21804 KB Output is correct
60 Correct 346 ms 21796 KB Output is correct
61 Correct 272 ms 21800 KB Output is correct
62 Correct 485 ms 21840 KB Output is correct
63 Correct 435 ms 21844 KB Output is correct
64 Correct 190 ms 21812 KB Output is correct
65 Correct 448 ms 21844 KB Output is correct
66 Correct 455 ms 21800 KB Output is correct
67 Correct 450 ms 21796 KB Output is correct
68 Correct 447 ms 21844 KB Output is correct
69 Correct 460 ms 21796 KB Output is correct
70 Correct 463 ms 21804 KB Output is correct
71 Execution timed out 2007 ms 42576 KB Time limit exceeded
72 Halted 0 ms 0 KB -