oj.uz

Submission #476490

# Submission time Handle Problem Language Result Execution time Memory
476490 2021-09-27T11:01:06 Z keta_tsimakuridze Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 631 ms 65540 KB 
#include<bits/stdc++.h>
#define f first
#define s second
////#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e6 + 5, mod = 1e9 + 7; // !
int t,dp1[N][22],dp2[N][22],L,q;
vector<int> cnt[4];
main(){
			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
            cin >> L >> q;
            string s;
            cin >> s;
            for(int i = 0; i < (1 << L); i++) { 
                        dp1[i][0] = s[i] - '0';
                        for(int j = 0; j < L; j++) {
                                    if(j) dp1[i][j] = dp1[i][j - 1];
                                    if((1 << j) & i) dp1[i][j] += dp1[i ^ (1 << j)][j];
                        }
            }
            for(int i = (1 << L) - 1; i >= 0; i--) {
                        dp2[i][0] = s[i] - '0';
                        for(int j = 0; j < L; j++) {
                                    if(j) dp2[i][j] = dp2[i][j - 1];
                                    if(!((1 << j) & i)) dp2[i][j] += dp2[i ^ (1 << j)][j];
                        }
            }
            while(q--) {
                        string t;
                        cin >> t;
                        int x = 0;
                        reverse(t.begin(),t.end());
                        int c = 0, a = 0, b = 0;
                        for(int i = 0; i < 3; i++) cnt[i].clear();
                        for(int i = 0; i < t.size(); i++) {
                                    if(t[i] == '0') cnt[0].push_back(i), a += 1 << i;
                                    else if(t[i] == '1') cnt[1].push_back(i),b += 1 << i;
                                    else cnt[2].push_back(i),c += 1 << i;
                        }
                        long long ans = 0;
                        if(cnt[2].size() < 7) {
                        		
                                    for(int i = c;; i = (i - 1) & c) {
                                                ans += s[i | b] - '0';
                                                if(!i) break;
                                    }
                        }
                        else if(cnt[1].size() < 7) {	
                                    int p = __builtin_popcount(b) % 2;
                                    for(int i = b;; i = (i - 1) & b) {
                                            ans += (__builtin_popcount(i) % 2 == p ? 1 : -1)
                                                    * dp1[i | c][L - 1];
                                            if(!i) break;
                                                    
                                    }
                        }
                        else {
 
                                    for(int i = a;; i = (i - 1) & a) {
                                            ans += (__builtin_popcount(i) % 2 == 0 ? 1 : -1)
                                                       * dp2[i | b][L - 1];
                                            if(!i) break;    
                                    }
                        }
                        cout << ans << "\n";
            }
 }

Compilation message

snake_escaping.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:36:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                         for(int i = 0; i < t.size(); i++) {
      |                                        ~~^~~~~~~~~~
snake_escaping.cpp:32:29: warning: unused variable 'x' [-Wunused-variable]
   32 |                         int x = 0;
      |                             ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 278 ms 4444 KB Output is correct
12 Correct 307 ms 4136 KB Output is correct
13 Correct 284 ms 3400 KB Output is correct
14 Correct 284 ms 3396 KB Output is correct
15 Correct 367 ms 4424 KB Output is correct
16 Correct 302 ms 3552 KB Output is correct
17 Correct 324 ms 3524 KB Output is correct
18 Correct 259 ms 5444 KB Output is correct
19 Correct 237 ms 2548 KB Output is correct
20 Correct 316 ms 4244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 278 ms 4444 KB Output is correct
12 Correct 307 ms 4136 KB Output is correct
13 Correct 284 ms 3400 KB Output is correct
14 Correct 284 ms 3396 KB Output is correct
15 Correct 367 ms 4424 KB Output is correct
16 Correct 302 ms 3552 KB Output is correct
17 Correct 324 ms 3524 KB Output is correct
18 Correct 259 ms 5444 KB Output is correct
19 Correct 237 ms 2548 KB Output is correct
20 Correct 316 ms 4244 KB Output is correct
21 Correct 631 ms 5740 KB Output is correct
22 Correct 417 ms 5892 KB Output is correct
23 Correct 348 ms 4852 KB Output is correct
24 Correct 337 ms 4680 KB Output is correct
25 Correct 338 ms 6668 KB Output is correct
26 Correct 363 ms 5164 KB Output is correct
27 Correct 379 ms 5096 KB Output is correct
28 Correct 216 ms 7688 KB Output is correct
29 Correct 276 ms 3756 KB Output is correct
30 Correct 428 ms 5916 KB Output is correct
31 Correct 398 ms 5696 KB Output is correct
32 Correct 370 ms 5812 KB Output is correct
33 Correct 310 ms 4620 KB Output is correct
34 Correct 351 ms 4792 KB Output is correct
35 Correct 437 ms 5188 KB Output is correct
36 Correct 204 ms 3700 KB Output is correct
37 Correct 373 ms 5688 KB Output is correct
38 Correct 302 ms 3700 KB Output is correct
39 Correct 347 ms 4908 KB Output is correct
40 Correct 375 ms 4700 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Runtime error 92 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 278 ms 4444 KB Output is correct
12 Correct 307 ms 4136 KB Output is correct
13 Correct 284 ms 3400 KB Output is correct
14 Correct 284 ms 3396 KB Output is correct
15 Correct 367 ms 4424 KB Output is correct
16 Correct 302 ms 3552 KB Output is correct
17 Correct 324 ms 3524 KB Output is correct
18 Correct 259 ms 5444 KB Output is correct
19 Correct 237 ms 2548 KB Output is correct
20 Correct 316 ms 4244 KB Output is correct
21 Correct 631 ms 5740 KB Output is correct
22 Correct 417 ms 5892 KB Output is correct
23 Correct 348 ms 4852 KB Output is correct
24 Correct 337 ms 4680 KB Output is correct
25 Correct 338 ms 6668 KB Output is correct
26 Correct 363 ms 5164 KB Output is correct
27 Correct 379 ms 5096 KB Output is correct
28 Correct 216 ms 7688 KB Output is correct
29 Correct 276 ms 3756 KB Output is correct
30 Correct 428 ms 5916 KB Output is correct
31 Correct 398 ms 5696 KB Output is correct
32 Correct 370 ms 5812 KB Output is correct
33 Correct 310 ms 4620 KB Output is correct
34 Correct 351 ms 4792 KB Output is correct
35 Correct 437 ms 5188 KB Output is correct
36 Correct 204 ms 3700 KB Output is correct
37 Correct 373 ms 5688 KB Output is correct
38 Correct 302 ms 3700 KB Output is correct
39 Correct 347 ms 4908 KB Output is correct
40 Correct 375 ms 4700 KB Output is correct
41 Runtime error 92 ms 65540 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -