oj.uz

Submission #121292

# Submission time Handle Problem Language Result Execution time Memory
121292 2019-06-26T09:51:07 Z bekzhan29 Fibonacci representations (CEOI18_fib) C++14
0 / 100
 3 ms 384 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -