oj.uz

Submission #552242

# Submission time Handle Problem Language Result Execution time Memory
552242 2022-04-22T20:46:07 Z urosk Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 827 ms 47480 KB 
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x)
// __builtin_clz(x) vodece nule
// __builtin_clzll(x)
// __builtin_ctz(x) nule na pocetku
// __builtin_ctzll(x)
// 2000000011
// 2000000033
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) ((ll)(a.size()))
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
#define here cerr<<"=============================================================================\n"
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define ceri2(a,l,r,n,m) {for(ll i = l;i<=r;i++){for(ll j = n;j<=m;j++) cerr<<a[i][j]<< " ";cerr<<endl;}}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
//#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
using namespace __gnu_pbds;

template<typename T> using vc = vector<T>;
template<typename T> using vvc = vc<vc<T>>;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
	if(x==mod) x = 0;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
#define maxn 2000005
ll n,q;
ll l;
ll sub[maxn],sup[maxn],btc[maxn];
ll s[maxn];
void tc(){
    cin >> l >> q;
    n = (1<<l)-1;
    string ss; cin >> ss;
    for(ll i = 0;i<=n;i++) s[i] = (ss[i]-'0');
    for(ll i = 0;i<=n;i++){
        btc[i] = __builtin_popcountll(i);
        sub[i] = sup[i] = s[i];
    }
    for(ll j = 0;j<l;j++){
        for(ll i = 0;i<=n;i++){
            if(((1<<j)&i)==0){
                sup[i]+=sup[i^(1<<j)];
            }else{
                sub[i]+=sub[i^(1<<j)];
            }
        }
    }
    while(q--){
        char ss[l+1]; scanf("%s",ss);
        ll a = 0,b = 0,c = 0;
        ll ca = 0,cb = 0,cc = 0;
        for(ll i = 0;i<l;i++){
            ll k = l-i-1;
            if(ss[i]=='0'){
                a|=(1<<k); ca++;
            }else if(ss[i]=='1'){
                b|=(1<<k); cb++;
            }else{
                c|=(1<<k); cc++;
            }
        }
        ll mc = min({ca,cb,cc});
        ll ans = 0;
        if(ca == mc){
            for(ll mask = a;mask!=0;mask=a&(mask-1)){
                ans+=(1-2*((btc[mask])&1))*sup[b|mask];
            }
            ans+=sup[b];
        }else if(cb==mc){
            for(ll mask = b;mask!=0;mask=b&(mask-1)){
                ans+=(1-2*((btc[mask])&1))*sub[c|(b^mask)];
            }
            ans += sub[c|b];
        }else{
            for(ll mask = c;mask!=0;mask=c&(mask-1)){
                ans+=s[b|mask];
            }
            ans+=s[b];
        }
        printf("%ld",ans);
        printf("\n");
    }
}
int main(){
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'void tc()':
snake_escaping.cpp:143:19: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'int' [-Wformat=]
  143 |         printf("%ld",ans);
      |                 ~~^  ~~~
      |                   |  |
      |                   |  int
      |                   long int
      |                 %d
snake_escaping.cpp: In function 'void setIO(std::string)':
snake_escaping.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:51:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void tc()':
snake_escaping.cpp:112:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         char ss[l+1]; scanf("%s",ss);
      |                       ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 286 ms 4580 KB Output is correct
12 Correct 259 ms 4272 KB Output is correct
13 Correct 283 ms 3532 KB Output is correct
14 Correct 322 ms 3540 KB Output is correct
15 Correct 259 ms 4556 KB Output is correct
16 Correct 323 ms 3672 KB Output is correct
17 Correct 301 ms 3632 KB Output is correct
18 Correct 224 ms 5520 KB Output is correct
19 Correct 281 ms 2556 KB Output is correct
20 Correct 274 ms 4272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 286 ms 4580 KB Output is correct
12 Correct 259 ms 4272 KB Output is correct
13 Correct 283 ms 3532 KB Output is correct
14 Correct 322 ms 3540 KB Output is correct
15 Correct 259 ms 4556 KB Output is correct
16 Correct 323 ms 3672 KB Output is correct
17 Correct 301 ms 3632 KB Output is correct
18 Correct 224 ms 5520 KB Output is correct
19 Correct 281 ms 2556 KB Output is correct
20 Correct 274 ms 4272 KB Output is correct
21 Correct 278 ms 4708 KB Output is correct
22 Correct 309 ms 4908 KB Output is correct
23 Correct 317 ms 3956 KB Output is correct
24 Correct 352 ms 3652 KB Output is correct
25 Correct 317 ms 5700 KB Output is correct
26 Correct 330 ms 4172 KB Output is correct
27 Correct 363 ms 4112 KB Output is correct
28 Correct 227 ms 6700 KB Output is correct
29 Correct 282 ms 2764 KB Output is correct
30 Correct 298 ms 4904 KB Output is correct
31 Correct 307 ms 4688 KB Output is correct
32 Correct 370 ms 4792 KB Output is correct
33 Correct 282 ms 3548 KB Output is correct
34 Correct 344 ms 3740 KB Output is correct
35 Correct 351 ms 4084 KB Output is correct
36 Correct 235 ms 2644 KB Output is correct
37 Correct 273 ms 4664 KB Output is correct
38 Correct 292 ms 2720 KB Output is correct
39 Correct 314 ms 3852 KB Output is correct
40 Correct 329 ms 3708 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 76 ms 19180 KB Output is correct
12 Correct 71 ms 20220 KB Output is correct
13 Correct 75 ms 20084 KB Output is correct
14 Correct 85 ms 20028 KB Output is correct
15 Correct 74 ms 20140 KB Output is correct
16 Correct 86 ms 20184 KB Output is correct
17 Correct 87 ms 20076 KB Output is correct
18 Correct 64 ms 20312 KB Output is correct
19 Correct 68 ms 19940 KB Output is correct
20 Correct 78 ms 20188 KB Output is correct
21 Correct 77 ms 20144 KB Output is correct
22 Correct 83 ms 20092 KB Output is correct
23 Correct 77 ms 20032 KB Output is correct
24 Correct 94 ms 20132 KB Output is correct
25 Correct 85 ms 20064 KB Output is correct
26 Correct 66 ms 20000 KB Output is correct
27 Correct 71 ms 20176 KB Output is correct
28 Correct 77 ms 19936 KB Output is correct
29 Correct 77 ms 20064 KB Output is correct
30 Correct 74 ms 20128 KB Output is correct
31 Correct 74 ms 20068 KB Output is correct
32 Correct 95 ms 20124 KB Output is correct
33 Correct 95 ms 20112 KB Output is correct
34 Correct 64 ms 20028 KB Output is correct
35 Correct 80 ms 20136 KB Output is correct
36 Correct 86 ms 20116 KB Output is correct
37 Correct 79 ms 20064 KB Output is correct
38 Correct 79 ms 20152 KB Output is correct
39 Correct 85 ms 20148 KB Output is correct
40 Correct 84 ms 20056 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 286 ms 4580 KB Output is correct
12 Correct 259 ms 4272 KB Output is correct
13 Correct 283 ms 3532 KB Output is correct
14 Correct 322 ms 3540 KB Output is correct
15 Correct 259 ms 4556 KB Output is correct
16 Correct 323 ms 3672 KB Output is correct
17 Correct 301 ms 3632 KB Output is correct
18 Correct 224 ms 5520 KB Output is correct
19 Correct 281 ms 2556 KB Output is correct
20 Correct 274 ms 4272 KB Output is correct
21 Correct 278 ms 4708 KB Output is correct
22 Correct 309 ms 4908 KB Output is correct
23 Correct 317 ms 3956 KB Output is correct
24 Correct 352 ms 3652 KB Output is correct
25 Correct 317 ms 5700 KB Output is correct
26 Correct 330 ms 4172 KB Output is correct
27 Correct 363 ms 4112 KB Output is correct
28 Correct 227 ms 6700 KB Output is correct
29 Correct 282 ms 2764 KB Output is correct
30 Correct 298 ms 4904 KB Output is correct
31 Correct 307 ms 4688 KB Output is correct
32 Correct 370 ms 4792 KB Output is correct
33 Correct 282 ms 3548 KB Output is correct
34 Correct 344 ms 3740 KB Output is correct
35 Correct 351 ms 4084 KB Output is correct
36 Correct 235 ms 2644 KB Output is correct
37 Correct 273 ms 4664 KB Output is correct
38 Correct 292 ms 2720 KB Output is correct
39 Correct 314 ms 3852 KB Output is correct
40 Correct 329 ms 3708 KB Output is correct
41 Correct 76 ms 19180 KB Output is correct
42 Correct 71 ms 20220 KB Output is correct
43 Correct 75 ms 20084 KB Output is correct
44 Correct 85 ms 20028 KB Output is correct
45 Correct 74 ms 20140 KB Output is correct
46 Correct 86 ms 20184 KB Output is correct
47 Correct 87 ms 20076 KB Output is correct
48 Correct 64 ms 20312 KB Output is correct
49 Correct 68 ms 19940 KB Output is correct
50 Correct 78 ms 20188 KB Output is correct
51 Correct 77 ms 20144 KB Output is correct
52 Correct 83 ms 20092 KB Output is correct
53 Correct 77 ms 20032 KB Output is correct
54 Correct 94 ms 20132 KB Output is correct
55 Correct 85 ms 20064 KB Output is correct
56 Correct 66 ms 20000 KB Output is correct
57 Correct 71 ms 20176 KB Output is correct
58 Correct 77 ms 19936 KB Output is correct
59 Correct 77 ms 20064 KB Output is correct
60 Correct 74 ms 20128 KB Output is correct
61 Correct 74 ms 20068 KB Output is correct
62 Correct 95 ms 20124 KB Output is correct
63 Correct 95 ms 20112 KB Output is correct
64 Correct 64 ms 20028 KB Output is correct
65 Correct 80 ms 20136 KB Output is correct
66 Correct 86 ms 20116 KB Output is correct
67 Correct 79 ms 20064 KB Output is correct
68 Correct 79 ms 20152 KB Output is correct
69 Correct 85 ms 20148 KB Output is correct
70 Correct 84 ms 20056 KB Output is correct
71 Correct 462 ms 44492 KB Output is correct
72 Correct 437 ms 44700 KB Output is correct
73 Correct 576 ms 43256 KB Output is correct
74 Correct 662 ms 43692 KB Output is correct
75 Correct 445 ms 45488 KB Output is correct
76 Correct 758 ms 43832 KB Output is correct
77 Correct 715 ms 43712 KB Output is correct
78 Correct 358 ms 47480 KB Output is correct
79 Correct 427 ms 41412 KB Output is correct
80 Correct 494 ms 44656 KB Output is correct
81 Correct 595 ms 44516 KB Output is correct
82 Correct 684 ms 43516 KB Output is correct
83 Correct 446 ms 42600 KB Output is correct
84 Correct 815 ms 43496 KB Output is correct
85 Correct 731 ms 43764 KB Output is correct
86 Correct 359 ms 41536 KB Output is correct
87 Correct 412 ms 44504 KB Output is correct
88 Correct 444 ms 41428 KB Output is correct
89 Correct 534 ms 43280 KB Output is correct
90 Correct 555 ms 43476 KB Output is correct
91 Correct 459 ms 42644 KB Output is correct
92 Correct 827 ms 43800 KB Output is correct
93 Correct 730 ms 43660 KB Output is correct
94 Correct 326 ms 41372 KB Output is correct
95 Correct 664 ms 43608 KB Output is correct
96 Correct 643 ms 43624 KB Output is correct
97 Correct 653 ms 43492 KB Output is correct
98 Correct 642 ms 43572 KB Output is correct
99 Correct 648 ms 43520 KB Output is correct
100 Correct 654 ms 43556 KB Output is correct