oj.uz

답안 #122509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122509 2019-06-28T13:29:42 Z egorlifar Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 638 ms 65536 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";


int l, q;
string s;
char c[1 << 20];
vector<char> st[1600228];
int ans[1594329];
int who[1600228];
int dp[1594329];
int pos[1594329];
long long g[30];
bool bad[1594329];
int prefs[1594329];


long long get(string s) {
	int it = 0;
	long long res = 0;
	for (auto x: s) {

		if (x == '?') {
			res += g[it] * 2;
		} else {
			res += g[it] * (x - '0');
		}
		it++;
	}
	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> l >> q;
	cin >> s;
	for (int i = 0; i < (1 << l); i++) {
		c[i] = s[i] - '0';
	}
	int t = 1;
	for (int i = 0; i < l - 7; i++) {
		t *= 3;
	}
		g[0] = 1;
	for (int i = 1; i <= 20; i++) {
		g[i] = g[i - 1] * 3;
	}
	if (l <= 7) {
		t = 1;
		for (int i = 0; i < l; i++) {
			t *= 3;
		}
		for (int mask = 0; mask < t; mask++) {
	        int id = mask;
	        bool was = false;
	        int cur = 0;
	        int r = 0;
	        int cur1 = 0;
	        int g = 1;
	        for (int t = 0; t < l; t++) {
	            int s = id % 3;
	            if (was) {
	                cur += s * g;
	                cur1 += s * g;
	            } else {
	                if (s == 2) {
	                    was = true;
	                    cur += 0 * g;
	                    cur1 += 1 * g;
	                } else {
	                    cur += s * g;
	                    cur1 += s * g;
	                    if (s) {
	                        r += (1 << (l - t - 1));
	                    }
	                }
	            }
	            id /= 3;
	            g *= 3;
	        }
	        if (!was) {
	            ans[mask] = c[r];
	        } else {
	            ans[mask] = ans[cur] + ans[cur1];
	        }
	    }
	    for (int it = 0; it < q; it++) {
	    	string k;
	    	cin >> k;
	        int x = get(k);
	      //  cout << "opa" << endl;
	        cout << ans[x] << '\n';
	    }   
	    return 0;
	}
	
	for (int it = 0; it < q; it++) {
		string f;
		cin >> f;
		long long x;
		x = get(f);
		for (int i = 0; i < l; i++) {
			st[it].pb(x % 3);
		//	cout << (int)st[it].back() << '\n';
			x /= 3;
		}
		reverse(all(st[it]));
		int cur = 1;
		for (int i = 7; i < l; i++) {
			who[it] += (int)st[it][i] * cur;
			cur *= 3;
		}
		for (int i = 0; i < 7; i++) {
			prefs[it] += (int)st[it][i] * g[i];
		}
	}	
	for (int i = 0; i < l - 7; i++) {
		for (int pre = 0; pre < (1 << i); pre++) {
			int rpre = 0;
			for (int k = 0; k < i; k++) {
				if (pre & (1 << k)) {
					rpre += g[k];
				}
			}
			for (int suff = 0; suff < g[l - 7 - i - 1]; suff++) {
				pos[rpre + 2 * g[i] + suff * g[i + 1]] = i + 1;
			}
		}
	}
	for (int mask = 0; mask < 128; mask++) {
		for (int i = 0; i < t; i++) {
			if (pos[i] == 0) {
				int curi = i;
				int nmask = mask;
				for (int j = 0; j < l - 7; j++) {
					int g = curi % 3;
					if (g) {
						nmask += 1 << (7 + j);
					}
					curi /= 3;
				}
				dp[i] = c[nmask];
			} else {
				dp[i] =dp[i - g[pos[i] - 1]] + dp[i - (g[pos[i] - 1] << 1)];
			}
		}
		for (int j = 0; j < g[7]; j++) {
			bad[j] = false;
			int cur = j;
			for (int f = 0; f < 7; f++) {
				int a = cur % 3;
				if (a != 2) {
					bool fs = ((mask & (1 << f)) != 0);
					if (fs != a) {
						bad[j] = true;
						break;
					}
				}
				cur /= 3;
			}
		}
		for (int it = 0; it < q; it++) {
            if (!bad[prefs[it]]) {
                ans[it] += dp[who[it]];
            }
		}
	}
	for (int it = 0; it < q; it++) {
		cout << ans[it] << '\n';
	}
	return 0; 		
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38016 KB Output is correct
2 Correct 39 ms 38012 KB Output is correct
3 Correct 38 ms 38192 KB Output is correct
4 Correct 37 ms 38016 KB Output is correct
5 Correct 38 ms 38008 KB Output is correct
6 Correct 38 ms 38136 KB Output is correct
7 Correct 37 ms 37980 KB Output is correct
8 Correct 37 ms 38016 KB Output is correct
9 Correct 37 ms 38016 KB Output is correct
10 Correct 39 ms 38016 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38016 KB Output is correct
2 Correct 39 ms 38012 KB Output is correct
3 Correct 38 ms 38192 KB Output is correct
4 Correct 37 ms 38016 KB Output is correct
5 Correct 38 ms 38008 KB Output is correct
6 Correct 38 ms 38136 KB Output is correct
7 Correct 37 ms 37980 KB Output is correct
8 Correct 37 ms 38016 KB Output is correct
9 Correct 37 ms 38016 KB Output is correct
10 Correct 39 ms 38016 KB Output is correct
11 Runtime error 319 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38016 KB Output is correct
2 Correct 39 ms 38012 KB Output is correct
3 Correct 38 ms 38192 KB Output is correct
4 Correct 37 ms 38016 KB Output is correct
5 Correct 38 ms 38008 KB Output is correct
6 Correct 38 ms 38136 KB Output is correct
7 Correct 37 ms 37980 KB Output is correct
8 Correct 37 ms 38016 KB Output is correct
9 Correct 37 ms 38016 KB Output is correct
10 Correct 39 ms 38016 KB Output is correct
11 Runtime error 319 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38016 KB Output is correct
2 Correct 39 ms 38012 KB Output is correct
3 Correct 38 ms 38192 KB Output is correct
4 Correct 37 ms 38016 KB Output is correct
5 Correct 38 ms 38008 KB Output is correct
6 Correct 38 ms 38136 KB Output is correct
7 Correct 37 ms 37980 KB Output is correct
8 Correct 37 ms 38016 KB Output is correct
9 Correct 37 ms 38016 KB Output is correct
10 Correct 39 ms 38016 KB Output is correct
11 Correct 553 ms 55620 KB Output is correct
12 Correct 591 ms 57860 KB Output is correct
13 Correct 587 ms 57760 KB Output is correct
14 Correct 555 ms 57752 KB Output is correct
15 Correct 638 ms 57880 KB Output is correct
16 Correct 637 ms 57680 KB Output is correct
17 Correct 552 ms 57752 KB Output is correct
18 Correct 547 ms 58076 KB Output is correct
19 Correct 492 ms 57628 KB Output is correct
20 Correct 524 ms 57776 KB Output is correct
21 Correct 559 ms 57912 KB Output is correct
22 Correct 573 ms 57680 KB Output is correct
23 Correct 537 ms 57624 KB Output is correct
24 Correct 514 ms 57764 KB Output is correct
25 Correct 531 ms 57760 KB Output is correct
26 Correct 527 ms 57724 KB Output is correct
27 Correct 618 ms 57868 KB Output is correct
28 Correct 601 ms 57572 KB Output is correct
29 Correct 569 ms 57752 KB Output is correct
30 Correct 509 ms 57752 KB Output is correct
31 Correct 509 ms 57624 KB Output is correct
32 Correct 525 ms 57776 KB Output is correct
33 Correct 561 ms 57708 KB Output is correct
34 Correct 493 ms 57596 KB Output is correct
35 Correct 516 ms 57672 KB Output is correct
36 Correct 527 ms 57696 KB Output is correct
37 Correct 564 ms 57752 KB Output is correct
38 Correct 532 ms 57712 KB Output is correct
39 Correct 523 ms 57812 KB Output is correct
40 Correct 527 ms 57752 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38016 KB Output is correct
2 Correct 39 ms 38012 KB Output is correct
3 Correct 38 ms 38192 KB Output is correct
4 Correct 37 ms 38016 KB Output is correct
5 Correct 38 ms 38008 KB Output is correct
6 Correct 38 ms 38136 KB Output is correct
7 Correct 37 ms 37980 KB Output is correct
8 Correct 37 ms 38016 KB Output is correct
9 Correct 37 ms 38016 KB Output is correct
10 Correct 39 ms 38016 KB Output is correct
11 Runtime error 319 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -