Submission #823058

#	Time	Username	Problem	Language	Result	Execution time	Memory
823058		MohamedAhmed04	Fibonacci representations (CEOI18_fib)	C++14	50 / 100	4059 ms	4364 KiB

fib

#include <bits/stdc++.h>

using namespace std ;

const int mod = 1e9 + 7 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Sub(int x , int y)
{
	int z = x - y ;
	if(z < 0)
		z += mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (1ll * x * y) % mod ;
}

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;

map<int , int>freq ;
multiset<int>s ;

void Insert(int x)
{
	if(x < 0)
		return ;
	if(x == 0)
		x = 1 ;
	s.insert(x) , freq[x]++ ;
	if(freq[x] == 2)
	{
		s.erase(x) , freq[x] = 0 ;
		Insert(x-2) , Insert(x+1) ;
	}
	else if(freq[x-1])
	{
		s.erase(x-1) , s.erase(x) ;
		freq[x-1] = freq[x] = 0 ;
		Insert(x+1) ;
	}
	else if(freq[x+1])
	{
		s.erase(x) , s.erase(x+1) ;
		freq[x] = freq[x+1] = 0 ;
		Insert(x+2) ;
	}
}

int dp[MAX][2] ;

int solve(int idx)
{
	vector<int>v = {0} ;
	for(auto &x : s)
		v.push_back(x) ;
	int sz = v.size() ;
	dp[1][0] = (v[1] + 1) / 2 - 1 , dp[1][1] = 1 ;
	for(int i = 2 ; i < sz ; ++i)
	{
		dp[i][1] = Add(dp[i-1][0] , dp[i-1][1]) ;
		int x = (v[i] - v[i-1] + 1) / 2 ;
		dp[i][0] = Mul(x-1 , Add(dp[i-1][0] , dp[i-1][1])) ;
		if((v[i] % 2) == (v[i-1] % 2))
			dp[i][0] = Add(dp[i][0] , dp[i-1][0]) ;
	}
	return Add(dp[sz-1][0] , dp[sz-1][1]) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n ; ++i)
	{
		Insert(arr[i]) ;
		cout<<solve(i)<<"\n" ;
	}
	return 0 ;
}		

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