Submission #114807

#	Time	Username	Problem	Language	Result	Execution time	Memory
114807		user202729	Fibonacci representations (CEOI18_fib)	C++17	0 / 100	2 ms	384 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 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';
	}
}
	

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