oj.uz

Submission #240363

# Submission time Handle Problem Language Result Execution time Memory
240363 2020-06-19T13:59:00 Z b00n0rp Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1879 ms 51652 KB 
// --------------------------------------------------<TEMPLATE>--------------------------------------------------
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN NEEDED)
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
// -------------------</optimizations>--------------------
 
// ---------------<Headers and namespaces>----------------
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
*/
// ---------------</Headers and namespaces>---------------
 
// -----------------<Defines and typedefs>----------------
// typedef tree<int,null_type,less<int>,rb_tree_tag, \
tree_order_statistics_node_update> indexed_set; // use less_equal for multiset
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)
 
typedef long double LD;
typedef long long ll;
// #define int ll
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
 
// -----<SCANF>-----
#define sfi(x) scanf("%d",&x);
#define sfi2(x,y) scanf("%d%d",&x,&y);
#define sfi3(x,y,z) scanf("%d%d%d",&x,&y,&z);
 
#define sfl(x) scanf("%lld",&x);
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define sfl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z);
#define sfl4(x,y,z,x1) scanf("%lld%lld%lld%lld",&x,&y,&z,&x1);
#define sfl5(x,y,z,x1,y1) scanf("%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1);
#define sfl6(x,y,z,x1,y1,z1) scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1,&z1);
 
#define sfs(x) scanf("%s",x);
#define sfs2(x,y) scanf("%s%s",x,y);
#define sfs3(x,y,z) scanf("%s%s%s",x,y,z);
// ----</SCANF>-----
 
// ----<PRINTF>-----
#define pfi(x) printf("%d\n",x);
#define pfi2(x,y) printf("%d %d\n",x,y);
#define pfi3(x,y,z) printf("%d %d %d\n",x,y,z);
 
#define pfl(x) printf("%lld\n",x);
#define pfl2(x,y) printf("%lld %lld\n",x,y);
#define pfl3(x,y,z) printf("%lld %lld %lld\n",x,y,z);
 
#define pfs(x) printf("%s\n",x);
#define pfs2(x,y) printf("%s %s\n",x,y);
#define pfs3(x,y,z) printf("%s %s %s\n",x,y,z);
 
#define pwe(x) printf("%lld ",x); // print without end
// ----</PRINTF>----
 
#define FLSH fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
// ----------------</Defines and typedefs>----------------
 
// -------------------<Debugging stuff>-------------------
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
// ------------------</Debugging stuff>-------------------
 
// ------------------------<Consts>-----------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
 
#ifdef int
const int INF=1e16;
#else
const int INF=1e9;
#endif
 
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
 
// -----------------------</Consts>-----------------------
 
// -------------------------<RNG>-------------------------
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
 
// ------------------------</RNG>-------------------------
// ----------------------<MATH>---------------------------
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
int add(int a, int b, int c = MOD){int res=a+b;return(res>=c?res-c:res);}
int mod_neg(int a, int b, int c = MOD){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
int mul(int a, int b, int c = MOD){ll res=(ll)a*b;return(res>=c?res%c:res);}
int muln(int a, int b, int c = MOD){ll res=(ll)a*b;return ((res%c)+c)%c;}
ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((LD)a*(LD)b)/(LD)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n = MOD){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
const int FACSZ = 1; // Make sure to change this
int fact[FACSZ],ifact[FACSZ];
void precom(int c = MOD){
    fact[0] = 1;
    FOR(i,1,FACSZ) fact[i] = mul(fact[i-1],i,c);
    ifact[FACSZ-1] = mod_inverse(fact[FACSZ-1],c);
    REPD(i,FACSZ-1){
        ifact[i] = mul(i+1,ifact[i+1],c);
    }
}
int ncr(int n,int r,int c = MOD){
    return mul(mul(ifact[r],ifact[n-r],c),fact[n],c);
} 
// ----------------------</MATH>--------------------------
// --------------------------------------------------</TEMPLATE>--------------------------------------------------
 
void solvethetestcase();
 
signed main(){
    // (UNCOMMENT FOR CIN/COUT) 
    FAST_IO
    PRECISION(10)
 
    int t = 1;
    // (UNCOMMENT FOR MULTIPLE TEST CASES) 
    // sfl(t);
    FOR(testcase,1,t+1){
        // (UNCOMMENT FOR CODEJAM) \
        printf("Case #%lld: ",testcase); 
        solvethetestcase();
    }
}   
 
int ST,LT; 
int n,q;
string s;
pii quer[1000005];
int pow3[21];
int dp[4782974];
int ans[1000005];
int last2[4782974];
bitset<2205> lol[2205];

void solvethetestcase(){
    pow3[0] = 1;
    FOR(i,1,18){
        pow3[i] = pow3[i-1]*3;
    }
    cin >> n >> q;
    cin >> s;
    if(n <= 10){
        ST = 0;
        LT = n;
    }
    else{
        ST = 7;
        LT = n-7;
    }
    REP(i,pow3[LT]){
        last2[i] = -1;
        int cur1 = i,cur2 = 0;
        while(cur1){
            if(cur1%3 == 2) last2[i] = cur2;
            cur2++;
            cur1 /= 3;
        }
        // trace(i,last2[i]);
    }
    
    REP(i,(1<<ST)){
        REP(j,pow3[ST]){
            int flag = 1;
            int cur1 = i,cur2 = j;
            REP(k,ST){
                if(cur2%3 != 2 and cur2%3 != cur1%2){
                    flag = 0;
                    break;
                }
                cur1 /= 2;
                cur2 /= 3;
            }
            lol[i][j] = flag;
        }
    }
    REP(i,q){
        string gg;
        cin >> gg;
        REP(j,ST){
            quer[i].F *= 3;
            if(gg[j] == '?') quer[i].F += 2;
            else quer[i].F += (gg[j]-'0');
        }
        FOR(j,ST,n){
            quer[i].S *= 3;
            if(gg[j] == '?') quer[i].S += 2;
            else quer[i].S += (gg[j]-'0');
        }
        // trace(i,quer[i].F,quer[i].S);
    }
    REP(i,(1<<ST)){
        fill(dp,dp+(pow3[LT]+1),0);
        REP(j,pow3[LT]){
            if(last2[j] == -1){
                int cur1 = j,cur2 = 0,cur3 = 0;
                while(cur1){
                    if(cur1%3) cur3 += (1<<cur2);
                    cur2++;
                    cur1 /= 3;
                }
                cur3 |= (i<<LT);
                // trace(cur3);
                dp[j] = (s[cur3]-'0');
            }
            else{
                dp[j] = dp[j-pow3[last2[j]]]+dp[j-pow3[last2[j]]*2];
            }
            // trace(j,dp[j]);
        }
        REP(j,q){
            if(lol[i][quer[j].F]) ans[j] += dp[quer[j].S];
        }
    }
    REP(i,q){
        cout << (ans[i]) << "\n";
    }
    // cout << runtime() << endl;
}

Compilation message

snake_escaping.cpp:4:1: warning: multi-line comment [-Wcomment]
 //(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
 ^
snake_escaping.cpp:54:1: warning: multi-line comment [-Wcomment]
 // typedef tree<int,null_type,less<int>,rb_tree_tag, \
 ^
snake_escaping.cpp:213:9: warning: multi-line comment [-Wcomment]
         // (UNCOMMENT FOR CODEJAM) \
         ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 880 KB Output is correct
11 Correct 241 ms 16608 KB Output is correct
12 Correct 257 ms 16352 KB Output is correct
13 Correct 225 ms 15596 KB Output is correct
14 Correct 232 ms 15608 KB Output is correct
15 Correct 266 ms 16552 KB Output is correct
16 Correct 239 ms 15912 KB Output is correct
17 Correct 244 ms 15712 KB Output is correct
18 Correct 202 ms 17532 KB Output is correct
19 Correct 192 ms 14584 KB Output is correct
20 Correct 256 ms 16248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 880 KB Output is correct
11 Correct 241 ms 16608 KB Output is correct
12 Correct 257 ms 16352 KB Output is correct
13 Correct 225 ms 15596 KB Output is correct
14 Correct 232 ms 15608 KB Output is correct
15 Correct 266 ms 16552 KB Output is correct
16 Correct 239 ms 15912 KB Output is correct
17 Correct 244 ms 15712 KB Output is correct
18 Correct 202 ms 17532 KB Output is correct
19 Correct 192 ms 14584 KB Output is correct
20 Correct 256 ms 16248 KB Output is correct
21 Correct 588 ms 16120 KB Output is correct
22 Correct 608 ms 16376 KB Output is correct
23 Correct 469 ms 15352 KB Output is correct
24 Correct 471 ms 15200 KB Output is correct
25 Correct 670 ms 17144 KB Output is correct
26 Correct 477 ms 15736 KB Output is correct
27 Correct 489 ms 15736 KB Output is correct
28 Correct 423 ms 18168 KB Output is correct
29 Correct 379 ms 14200 KB Output is correct
30 Correct 607 ms 16376 KB Output is correct
31 Correct 518 ms 16248 KB Output is correct
32 Correct 508 ms 16248 KB Output is correct
33 Correct 435 ms 15096 KB Output is correct
34 Correct 526 ms 15224 KB Output is correct
35 Correct 485 ms 15608 KB Output is correct
36 Correct 319 ms 14136 KB Output is correct
37 Correct 533 ms 16188 KB Output is correct
38 Correct 391 ms 14136 KB Output is correct
39 Correct 507 ms 15508 KB Output is correct
40 Correct 477 ms 15352 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 880 KB Output is correct
11 Correct 601 ms 14824 KB Output is correct
12 Correct 577 ms 14952 KB Output is correct
13 Correct 597 ms 14812 KB Output is correct
14 Correct 590 ms 14872 KB Output is correct
15 Correct 614 ms 14940 KB Output is correct
16 Correct 547 ms 14848 KB Output is correct
17 Correct 605 ms 14848 KB Output is correct
18 Correct 571 ms 15076 KB Output is correct
19 Correct 629 ms 14748 KB Output is correct
20 Correct 580 ms 14944 KB Output is correct
21 Correct 600 ms 14876 KB Output is correct
22 Correct 590 ms 14876 KB Output is correct
23 Correct 587 ms 14816 KB Output is correct
24 Correct 606 ms 14844 KB Output is correct
25 Correct 603 ms 14944 KB Output is correct
26 Correct 565 ms 14744 KB Output is correct
27 Correct 591 ms 14872 KB Output is correct
28 Correct 722 ms 14748 KB Output is correct
29 Correct 602 ms 14824 KB Output is correct
30 Correct 584 ms 14812 KB Output is correct
31 Correct 574 ms 14820 KB Output is correct
32 Correct 647 ms 14816 KB Output is correct
33 Correct 589 ms 14872 KB Output is correct
34 Correct 611 ms 14748 KB Output is correct
35 Correct 563 ms 15124 KB Output is correct
36 Correct 606 ms 14872 KB Output is correct
37 Correct 555 ms 14820 KB Output is correct
38 Correct 572 ms 14812 KB Output is correct
39 Correct 611 ms 14852 KB Output is correct
40 Correct 576 ms 14828 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 880 KB Output is correct
11 Correct 241 ms 16608 KB Output is correct
12 Correct 257 ms 16352 KB Output is correct
13 Correct 225 ms 15596 KB Output is correct
14 Correct 232 ms 15608 KB Output is correct
15 Correct 266 ms 16552 KB Output is correct
16 Correct 239 ms 15912 KB Output is correct
17 Correct 244 ms 15712 KB Output is correct
18 Correct 202 ms 17532 KB Output is correct
19 Correct 192 ms 14584 KB Output is correct
20 Correct 256 ms 16248 KB Output is correct
21 Correct 588 ms 16120 KB Output is correct
22 Correct 608 ms 16376 KB Output is correct
23 Correct 469 ms 15352 KB Output is correct
24 Correct 471 ms 15200 KB Output is correct
25 Correct 670 ms 17144 KB Output is correct
26 Correct 477 ms 15736 KB Output is correct
27 Correct 489 ms 15736 KB Output is correct
28 Correct 423 ms 18168 KB Output is correct
29 Correct 379 ms 14200 KB Output is correct
30 Correct 607 ms 16376 KB Output is correct
31 Correct 518 ms 16248 KB Output is correct
32 Correct 508 ms 16248 KB Output is correct
33 Correct 435 ms 15096 KB Output is correct
34 Correct 526 ms 15224 KB Output is correct
35 Correct 485 ms 15608 KB Output is correct
36 Correct 319 ms 14136 KB Output is correct
37 Correct 533 ms 16188 KB Output is correct
38 Correct 391 ms 14136 KB Output is correct
39 Correct 507 ms 15508 KB Output is correct
40 Correct 477 ms 15352 KB Output is correct
41 Correct 601 ms 14824 KB Output is correct
42 Correct 577 ms 14952 KB Output is correct
43 Correct 597 ms 14812 KB Output is correct
44 Correct 590 ms 14872 KB Output is correct
45 Correct 614 ms 14940 KB Output is correct
46 Correct 547 ms 14848 KB Output is correct
47 Correct 605 ms 14848 KB Output is correct
48 Correct 571 ms 15076 KB Output is correct
49 Correct 629 ms 14748 KB Output is correct
50 Correct 580 ms 14944 KB Output is correct
51 Correct 600 ms 14876 KB Output is correct
52 Correct 590 ms 14876 KB Output is correct
53 Correct 587 ms 14816 KB Output is correct
54 Correct 606 ms 14844 KB Output is correct
55 Correct 603 ms 14944 KB Output is correct
56 Correct 565 ms 14744 KB Output is correct
57 Correct 591 ms 14872 KB Output is correct
58 Correct 722 ms 14748 KB Output is correct
59 Correct 602 ms 14824 KB Output is correct
60 Correct 584 ms 14812 KB Output is correct
61 Correct 574 ms 14820 KB Output is correct
62 Correct 647 ms 14816 KB Output is correct
63 Correct 589 ms 14872 KB Output is correct
64 Correct 611 ms 14748 KB Output is correct
65 Correct 563 ms 15124 KB Output is correct
66 Correct 606 ms 14872 KB Output is correct
67 Correct 555 ms 14820 KB Output is correct
68 Correct 572 ms 14812 KB Output is correct
69 Correct 611 ms 14852 KB Output is correct
70 Correct 576 ms 14828 KB Output is correct
71 Correct 1239 ms 30872 KB Output is correct
72 Correct 1284 ms 42880 KB Output is correct
73 Correct 1196 ms 39744 KB Output is correct
74 Correct 1350 ms 40548 KB Output is correct
75 Correct 1520 ms 44716 KB Output is correct
76 Correct 1356 ms 41232 KB Output is correct
77 Correct 1370 ms 40896 KB Output is correct
78 Correct 999 ms 48692 KB Output is correct
79 Correct 1010 ms 36640 KB Output is correct
80 Correct 1235 ms 42904 KB Output is correct
81 Correct 1538 ms 42644 KB Output is correct
82 Correct 1366 ms 40564 KB Output is correct
83 Correct 1116 ms 39068 KB Output is correct
84 Correct 1356 ms 40576 KB Output is correct
85 Correct 1420 ms 40908 KB Output is correct
86 Correct 907 ms 36716 KB Output is correct
87 Correct 1231 ms 37548 KB Output is correct
88 Correct 997 ms 34480 KB Output is correct
89 Correct 1272 ms 36132 KB Output is correct
90 Correct 1452 ms 50204 KB Output is correct
91 Correct 1091 ms 50560 KB Output is correct
92 Correct 1405 ms 51652 KB Output is correct
93 Correct 1543 ms 51556 KB Output is correct
94 Correct 904 ms 49432 KB Output is correct
95 Correct 1377 ms 51648 KB Output is correct
96 Correct 1395 ms 51516 KB Output is correct
97 Correct 1879 ms 51636 KB Output is correct
98 Correct 1370 ms 51608 KB Output is correct
99 Correct 1347 ms 51516 KB Output is correct
100 Correct 1329 ms 51632 KB Output is correct