Submission #121292

#	Time	Username	Problem	Language	Result	Execution time	Memory
121292		bekzhan29	Fibonacci representations (CEOI18_fib)	C++14	0 / 100	3 ms	384 KiB

fib

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 1e18
#define mod 1000000007
#define eps 1e-6
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
void read(ll &x)
{
	scanf("%lld",&x);
}
void read(ll &x, ll &y)
{
	scanf("%lld%lld",&x,&y);
}
void read(ll &x, ll &y, ll &z)
{
	scanf("%lld%lld%lld",&x,&y,&z);
}
void print(ll x)
{
	printf("%lld ",x);
}
void println(ll x)
{
	printf("%lld\n",x);
}
const ll N=300100;
ll n,x,last,cnt,ans,sum;
map<ll,ll>v;
void che(ll x)
{
	if(x>1&&v.count(x)&&v.count(x-1))
	{
		v[x+1]++;
		v.erase(x);
		v.erase(x-1);
		che(x+1);
		return;
	}
	if(v.count(x)&&v.count(x+1))
	{
		v[x+2]++;
		v.erase(x);
		v.erase(x+1);
		che(x+2);
		return;
	}
	if(!v.count(x)||v[x]<2)
		return;
	if(x==1)
	{
		v[x+1]+=(v[x]>>1);
		v[x]&=1;
		if(v[x]==0)
			v.erase(x);
		che(x+1);
		return;
	}
	if(x==2)
	{
		v[x-1]+=(v[x]>>1);
		v[x+1]+=(v[x]>>1);
		v[x]&=1;
		if(v[x]==0)
			v.erase(x);
		che(x-1);
		che(x+1);
		return;
	}
	v[x-2]+=(v[x]>>1);
	v[x+1]+=(v[x]>>1);
	v[x]&=1;
	if(v[x]==0)
			v.erase(x);
	che(x-2);
	che(x+1);
}
int main()
{
	cin>>n;
	if(n>100)
		return 0;
	for(ll i=1;i<=n;i++)
	{
		read(x);
		v[x]++;
		che(x);
		last=cnt=0;
		ans=sum=1;
		for(auto it:v)
		{
			assert(it.second>0);
			assert(it.first==1||it.first-last>1);
			if(it.first-2!=last)
			{
				ans*=sum;
				ans%=mod;
				sum=1;
				cnt=(it.first-last-1)/2;
			}
			last=it.first;
			sum+=cnt;
			if(sum>=mod)
				sum-=mod;
		}
		ans*=sum;
		ans%=mod;
		println(ans);
	}
}

Compilation message (stderr)

fib.cpp: In function 'void read(ll&)':
fib.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&x);
  ~~~~~^~~~~~~~~~~
fib.cpp: In function 'void read(ll&, ll&)':
fib.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&x,&y);
  ~~~~~^~~~~~~~~~~~~~~~~~
fib.cpp: In function 'void read(ll&, ll&, ll&)':
fib.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&x,&y,&z);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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