Submission #287542

#	Time	Username	Problem	Language	Result	Execution time	Memory
287542		TadijaSebez	Fibonacci representations (CEOI18_fib)	C++11	15 / 100	4065 ms	2484 KiB

fib

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
map<int,int> cnt;
void Inc(int a){
	cnt[a]++;
	while(cnt[a-1]&&cnt[a]){
		cnt[a-1]--;
		cnt[a]--;
		cnt[a+1]++;
		a++;
		if(!(cnt[a-1]&&cnt[a]))a++;
	}
}
void Fix(){
	if(cnt[1]>1){
		cnt[1]-=2;
		Inc(2);
	}
	if(cnt[2]>1){
		cnt[2]-=2;
		Inc(1);
		Inc(3);
	}
}
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%i",&a);
		Inc(a);
		Fix();
		int mx=0;
		int dp[2]={1,0},las=0;
		for(auto it:cnt){
			int j=it.first;
			if(!it.second)continue;
			if(it.second==1){
				int d0=add(dp[1],dp[0]);
				int sz=j-las-1;
				int d1=mul(dp[0],sz/2);
				sz++;
				d1=add(d1,mul(dp[1],sz/2));
				las=j;
				dp[0]=d0;
				dp[1]=d1;
			}else if(it.second==2){
				int sz=j-las-1;
				int d0=add(mul(dp[0],sz/2),mul(dp[1],(sz+1)/2));
				dp[0]=d0;
				dp[1]=0;
			}else dp[0]=dp[1]=0;
		}
		int ans=add(dp[0],dp[1]);
		printf("%i\n",ans);
	}
	return 0;
}

Compilation message (stderr)

fib.cpp: In function 'int main()':
fib.cpp:37:7: warning: unused variable 'mx' [-Wunused-variable]
   37 |   int mx=0;
      |       ^~
fib.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%i",&a);
      |   ~~~~~^~~~~~~~~

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