Seletiva IOI 2014

permutacao.cpp

// Ivan Carvalho
// Permutação - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
#define gc getchar_unlocked
inline void print(int n){
	char buf[11];
	buf[10] = ' ';
	int i = 9;
	while (n){
		buf[i--] = n % 10 + '0';
		n /= 10;
	}
	while (buf[i] != ' ') putchar_unlocked(buf[++i]);
}
inline void getint(int &x){
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
#define LSOne(S) (S & (-S))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MOD1 = 1e9 + 9;
const ll prime1 = 999983;
const ll MOD2 = 1e9 + 7;
const ll prime2 = 999979;
const ll invprime1 = 943912055;
const ll invprime2 = 672490127;
const int MAXN = 1e6 + 10;
ll pot1[MAXN],hash1[MAXN],hash2;
int vetor[MAXN],n,ondeesta[MAXN];
vector<int> resposta;
inline void update(int idx,ll delta){
	while(idx < MAXN){
		hash1[idx] += delta;
		hash1[idx] %= MOD1;
		idx += LSOne(idx);
	}
}
inline ll read(int idx){
	ll ans = 0;
	while(idx > 0){
		ans += hash1[idx];
		ans %= MOD1;
		idx -= LSOne(idx);
	}
	return ans;
}
inline ll query(int l,int r){
	if(l > r) return 0;
	return read(r) - read(l - 1);
}
int main(){
	getint(n);
	pot1[0] = 1LL;
	for(int i = 1;i<=n;i++){
		getint(vetor[i]);
		pot1[i] = (prime1 * pot1[i-1]) % MOD1;
		update(i, (pot1[i]*vetor[i]));
		ondeesta[vetor[i]] = i;
	}
	for(int i = 1;i<n;i++){
		int davez;
		getint(davez);
		hash2 += (davez * pot1[i]);
		hash2 %= MOD1;
	}
	for(int i = n;i>=1;i--){
		ll encontra = ondeesta[i];
		update(encontra, -pot1[encontra]);
		ll meuval = query(1,encontra-1) + (invprime1*query(encontra + 1,n) % MOD1);
		meuval %= MOD1;
		if(meuval < 0) meuval += MOD1;
		if(meuval == hash2) resposta.push_back(i);
	}
	while(!resposta.empty()){
		print(resposta.back());
		resposta.pop_back();
	}
	printf("\n");
	return 0;
}