Submission #114809

#	Time	Username	Problem	Language	Result	Execution time	Memory
114809		user202729	Fibonacci representations (CEOI18_fib)	C++17	50 / 100	4005 ms	3112 KiB

fib

#include<iostream>
#include<vector>
#include<cassert>
#include<set>

#ifdef _GLIBCXX_DEBUG
#include<sstream>
#define cin cin_
namespace std{
	std::stringstream cin(R"(
4
4 1 1 5
	)");
};
#endif

int constexpr MOD=1000000007;

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int n;std::cin>>n;
	std::vector<int> a(n);
	for(int& x:a){
		std::cin>>x;
		--x;
	}

	std::set<int> s; // zeckendorf repr

	std::vector<int> stk;
	for(int x:a){
		// add F[x] to s
		assert(stk.empty());
		stk.push_back(x);
#define x _DONT_USE_THIS

		do{ // TODO: reduce (nnum*log) to (nnum+log)
			int y=stk.back();stk.pop_back();
			auto it=s.lower_bound(y-1);
			if(it==s.end()||*it>y+1){
				s.insert(y);
			}else if(*it<y){
				assert(*it==y-1);
				s.erase(it);
				stk.push_back(y+1);
			}else if(*it==y){
				s.erase(it);
				stk.push_back(y+1);
				if(y==0){ // assume F[-1] == 1 and F[-2] == 0
					assert(y-2 == -2);
					continue;
				}else
					stk.push_back(std::max(0,y-2));
			}else{
				assert(*it==y+1);
				s.erase(it);
				stk.push_back(y+2);
			}
		}while(!stk.empty());

		// for(int y:s)std::cout<<y<<' ';
		// std::cout<<'\n';

		int const n=s.size();
		std::vector<int> f0(n),f1(n);
		assert(n>0);
		int s0=*s.begin();
		f0[0]=s0/2u; // [i] = number of repr of [0..i] -> F{x | x<s[i]}
		f1[0]=1; // ~~~ but with F(s[i])

		auto it=s.begin();++it;
		for(int i=1,
				last=s0 /* s[i-1] */;
				it!=s.end();++i,last=*it++){
			int diff=*it-last; // s[i]-s[i-1]
			f1[i]=(
					f0[i-1]+f1[i-1]
				)%MOD;
			f0[i]=(
					f0[i-1]*(diff/2ull)+f1[i-1]*((diff-1)/2ull)
				)%MOD;
		}

		std::cout<<(f0.back()+f1.back())%MOD<<'\n';
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35