oj.uz

Submission #1084963

# Submission time Handle Problem Language Result Execution time Memory
1084963 2024-09-07T09:10:00 Z 8pete8 Fibonacci representations (CEOI18_fib) C++17
50 / 100
 4000 ms 2992 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5+5,inf=1e9,minf=-1e18,lg=30,valbound=1e9;
//#undef int
int k,m,q,p,h,w,n;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);	
	freopen((name+".in").c_str(),"r",stdin);	
	freopen((name+".out").c_str(),"w",stdout);
}
int val[mxn+10];
map<int,int>on;
void simplify(){
	bool yes=1;
	int cnt=0;
	while(yes){
		cnt++;
		vector<int>del;
		for(auto &i:on){
			if(i.s==0)continue;
			if(i.s>1&&i.f>2){
				if(i.s/2){
					on[i.f+1]+=(i.s)/2;
					on[i.f-2]+=(i.s)/2;
				}
				i.s%=2;
				if(i.s==0)del.pb(i.f);
			}
			else if(i.s>1&&i.f==2){
				if(i.s/2){
					on[i.f+1]+=(i.s)/2;
					on[i.f-1]+=(i.s)/2;
				}
				i.s%=2;
				if(i.s==0)del.pb(i.f);
			}
		}
		for(auto &i:on){
			if(i.s==0)continue;
			if(i.f==1){
				if(i.s/2)on[2]+=(i.s/2);
				i.s%=2;
				if(i.s==0)del.pb(i.f);
			}
			else{
				int x=min(on[i.f-1],i.s);
				if(x){
					on[i.f+1]+=x;
					i.s-=x;
					on[i.f-1]-=x;
				}
				if(on[i.f-1]==0)del.pb(i.f-1);
				if(i.s==0)del.pb(i.f);
			}
		}
		sort(all(del));
		del.erase(unique(all(del)),del.end());
		for(auto i:del)on.erase(i);
		bool nxt=0;
		for(auto i:on)if(i.s>1)nxt=1;
		yes=nxt;
	}
}
int dp[2];
int cal(int a,int b){return ((b-a-1)/2);}
int get(){
	int last=-1;
	dp[0]=0,dp[1]=0;
	for(auto i:on){
		if(last==-1){
			dp[0]=1;
			dp[1]=cal(0,i.f);
		}
		else{
			int x=(dp[0]+dp[1])%mod,y=0;
			y=(dp[0]*cal(last,i.f))%mod;
			y=(y+(dp[1]*cal(last-1,i.f))%mod)%mod;
			dp[0]=x,dp[1]=y;
		}
		last=i.f;
	}
	return (dp[0]+dp[1])%mod;
} 
int32_t main(){
	fastio
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1;i<=n;i++){
		on[val[i]]++;
		simplify();
		cout<<get()<<'\n';
	}
	
}
/*
for a number x with occurences y
we can make the number x+z using fib(z+1) xs
we can push the number and get a set of number with only 1 occurence

what to do with these distinct number?

for a number x 
we can split it into x-1,x-2
if we keep spliting to x-1,x-3,x-4
x-1,x-3,x-5,x-6
we can see the odd number wont be able to split as it will result in having the same number
so there has to be an even number y that is the end
we can do dp[i][split?]
dp[i][not split]=(sum of dp[i-1])
dp[i][split]={
	dp[i-1][not split]*(number of usable y in range (val[i-1],val[i]))
	+
	dp[i-1][split]*(number of usable y in range (val[i-1]-1,val[i]))
}
would this work?
*/

Compilation message

fib.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
fib.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
fib.cpp:45:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 | void simplify(){
      |               ^
fib.cpp:97:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   97 | int cal(int a,int b){return ((b-a-1)/2);}
      |                    ^
fib.cpp:98:9: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   98 | int get(){
      |         ^
fib.cpp:116:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  116 | int32_t main(){
      |              ^
fib.cpp: In function 'void setIO(std::string)':
fib.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fib.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 8 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 2 ms 348 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Execution timed out 4067 ms 2992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 8 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 2 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Execution timed out 4067 ms 2992 KB Time limit exceeded
26 Halted 0 ms 0 KB -