Submission #521607

#	Time	Username	Problem	Language	Result	Execution time	Memory
521607		AdamGS	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	2017 ms	56620 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
string S;
void solve(vector<ll>&V, vector<int>&ans, int l, int r, ll akt) {
	if(!V.size()) return;
	if(l==r) {
		ans[0]=S[l]-'0';
		return;
	}
	int ile1=0, ile2=0, ile3=0;
	rep(i, V.size()) {
		if(V[i]/akt==0) ++ile1;
		else if(V[i]/akt==1) ++ile2;
		else ++ile3;
	}
	vector<ll>zero, jeden;
	int l1=0, l2=0;
	while(l1<ile1 || l2<ile2) {
		if(l1<ile1) {
			if(l2<ile2) {
				if(V[l1]%akt<=V[ile1+l2]%akt) {
					if(!zero.size() || zero.back()!=V[l1]%akt) zero.pb(V[l1]%akt);
					++l1;
				} else {
					if(!zero.size() || zero.back()!=V[ile1+l2]%akt) zero.pb(V[ile1+l2]%akt);
					++l2;
				}
			} else {
				if(!zero.size() || zero.back()!=V[l1]%akt) zero.pb(V[l1]%akt);
				++l1;
			}
		} else {
			if(!zero.size() || zero.back()!=V[ile1+l2]%akt) zero.pb(V[ile1+l2]%akt);
			++l2;
		}
	}
	vector<int>zans(zero.size());
	solve(zero, zans, l, (l+r)/2, akt/3);
	l1=0;
	rep(i, ile1) {
		while(zero[l1]<V[i]%akt) ++l1;
		ans[i]+=zans[l1];
	}
	l1=0;
	rep(i, ile2) {
		while(zero[l1]<V[ile1+i]%akt) ++l1;
		ans[ile1+i]+=zans[l1];
	}
	l1=0; l2=0;
	while(l1<ile1 || l2<ile3) {
		if(l1<ile1) {
			if(l2<ile3) {
				if(V[l1]%akt<=V[ile1+ile2+l2]%akt) {
					if(!jeden.size() || jeden.back()!=V[l1]%akt) jeden.pb(V[l1]%akt);
					++l1;
				} else {
					if(!jeden.size() || jeden.back()!=V[ile1+ile2+l2]%akt) jeden.pb(V[ile1+ile2+l2]%akt);
					++l2;
				}
			} else {
				if(!jeden.size() || jeden.back()!=V[l1]%akt) jeden.pb(V[l1]%akt);
				++l1;
			}
		} else {
			if(!jeden.size() || jeden.back()!=V[ile1+ile2+l2]%akt) jeden.pb(V[ile1+ile2+l2]%akt);
			++l2;
		}
	}
	vector<int>jans(jeden.size());
	solve(jeden, jans, (l+r)/2+1, r, akt/3);
	l1=0;
	rep(i, ile1) {
		while(jeden[l1]<V[i]%akt) ++l1;
		ans[i]+=jans[l1];
	}
	l1=0;
	rep(i, ile3) {
		while(jeden[l1]<V[ile1+ile2+i]%akt) ++l1;
		ans[ile1+ile2+i]+=jans[l1];
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int l, q, n=1;
	cin >> l >> q >> S;
	rep(i, l) n*=2;
	pair<ll,int>T[q];
	rep(i, q) {
		string x;
		cin >> x;
		ll p=0;
		for(auto j : x) {
			p*=3;
			if(j=='0') ++p;
			if(j=='1') p+=2;
		}
		T[i]={p, i};
	}
	sort(T, T+q);
	vector<ll>V(q);
	vector<int>ans(q);
	rep(i, q) V[i]=T[i].st;
	ll akt=1;
	rep(i, l-1) akt*=3;
	solve(V, ans, 0, n-1, akt);
	rep(i, q) T[i]={T[i].nd, ans[i]};
	sort(T, T+q);
	rep(i, q) cout << T[i].nd << '\n';
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve(std::vector<long long int>&, std::vector<int>&, int, int, ll)':
snake_escaping.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
snake_escaping.cpp:18:2: note: in expansion of macro 'rep'
   18 |  rep(i, V.size()) {
      |  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25