oj.uz

Submission #70659

# Submission time Handle Problem Language Result Execution time Memory
70659 2018-08-23T08:17:55 Z 노영훈(#2185) Fibonacci representations (CEOI18_fib) C++11
35 / 100
 415 ms 11208 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, MOD=1e9+7, inf=2e9;

int n, A[MX];

void norm(map<int, int> &cnt){
	vector<int> V;
	for(pii p:cnt)
		if(p.second==0) V.push_back(p.first);
	for(int x:V) cnt.erase(x);
}

void check2(map<int, int> &cnt){
	int pos=-1;
	for(pii p:cnt) if(p.second==2) pos=p.first;
	if(pos<0) return;

	while(true){
		if(cnt[pos]<=1) return;
		if(pos==1){ cnt.erase(1), cnt[2]=1; break; }
		if(pos==2){ cnt.erase(2), cnt[1]=cnt[3]=1; break; }
		cnt.erase(pos);
		cnt[pos+1]++, cnt[pos-2]++;
		pos-=2;
	}
}

void check11(map<int, int> &cnt){

	int lft=-1, rig=-1;

	for(auto it=next(cnt.begin()); it!=cnt.end(); it++)
		if(prev(it)->first == it->first-1) lft = prev(it)->first;

	if(lft<0) return;

	for(int i=lft, tmp=0; i<=inf; i++){
		if(cnt[i]==0) tmp++;
		else tmp=0;
		if(tmp==2){ rig=i; break; }
	}

	for(int i=lft; i<=rig; i++) cnt.erase(i);
	cnt[rig-1]=1;
}

void check(map<int, int> &cnt){
	norm(cnt);
	check2(cnt);
	norm(cnt);
	check11(cnt);
	norm(cnt);
}

void solve4(){
	map<int, int> cnt;
	int D[151], E[151];
	for(int i=1; i<=n; i++){
		cnt[A[i]]++;
		cnt.erase(0);
		check(cnt);
		cnt[0]=1;


		D[0]=1, E[0]=0;
		for(int i=1; i<=150; i++) D[i]=E[i]=0;
		
		int ans=0, pos=1;
		for(auto it=next(cnt.begin()); it!=cnt.end(); it++, pos++){
			int i=it->first, j=prev(it)->first;
			D[pos] = (D[pos-1] + E[pos-1]) % MOD;
			E[pos] = (ll(i-j-1)/2 * D[pos-1] + ll(i-j)/2 * E[pos-1]) % MOD;
			ans = (D[pos]+E[pos])%MOD;
		}
		cout<<ans<<'\n';
	}
}


struct mat22{
	int A[2][2]={1,0,0,1};
	mat22(){}
	mat22(int c, int d){
		A[0][0]=1, A[0][1]=1, A[1][0]=c, A[1][1]=d;
	}
	mat22 operator * (const mat22 m) const {
		mat22 res;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]=0;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++)
			res.A[i][j]+=1LL*A[i][k]*m.A[k][j]%MOD;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]%=MOD;
		return res;
	}
	void show(){
		cout<<A[0][0]<<' '<<A[0][1]<<'\n'<<A[1][0]<<' '<<A[1][1]<<'\n';
	}
} tree[1<<18];

void upt(int v, int s, int e, int x, mat22 &m){
	if(x<s || e<x) return;
	if(s==e){
		tree[v]=m; return;
	}
	upt(v*2,s,(s+e)/2,x,m);
	upt(v*2+1,(s+e)/2+1,e,x,m);
	tree[v]=tree[v*2+1]*tree[v*2];
}

void upt(int pos, mat22 m){
	upt(1,1,n,pos,m);
}
int get(){
	return (tree[1].A[0][0]+tree[1].A[1][0])%MOD;
}

void solve5(){
	vector<int> X={0};
	for(int i=1; i<=n; i++) X.push_back(A[i]);
	set<int> S; S.insert(0);
	sort(X.begin(), X.end());

	for(int i=1; i<=n; i++){
		int a=A[i], pos=lower_bound(X.begin(), X.end(), a)-X.begin();
		
		auto it=S.lower_bound(a);
		int z=a-*prev(it)-1;

		upt(pos, mat22(z/2, (z+1)/2));

		if(it!=S.end()){
			int b=*it, sop=lower_bound(X.begin(), X.end(), b)-X.begin();
			int w=b-a-1;
			upt(sop, mat22(w/2, (w+1)/2));
		}

		S.insert(a);
		cout<<get()<<'\n';
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;

	int mx=0;
	for(int i=1; i<=n; i++) cin>>A[i], mx=max(mx, A[i]);

	if(n<=100){
		solve4();
		return 0;
//		if(mx<=100) solve12();
//		else solve3();
//		return 0;
	}
	else{
		solve5();
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4584 KB Output is correct
3 Correct 6 ms 4660 KB Output is correct
4 Correct 6 ms 4660 KB Output is correct
5 Correct 9 ms 4660 KB Output is correct
6 Correct 6 ms 4660 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4584 KB Output is correct
3 Correct 6 ms 4660 KB Output is correct
4 Correct 6 ms 4660 KB Output is correct
5 Correct 9 ms 4660 KB Output is correct
6 Correct 6 ms 4660 KB Output is correct
7 Incorrect 6 ms 4660 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4692 KB Output is correct
2 Correct 6 ms 4692 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4584 KB Output is correct
3 Correct 6 ms 4660 KB Output is correct
4 Correct 6 ms 4660 KB Output is correct
5 Correct 9 ms 4660 KB Output is correct
6 Correct 6 ms 4660 KB Output is correct
7 Incorrect 6 ms 4660 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4692 KB Output is correct
2 Correct 415 ms 11176 KB Output is correct
3 Correct 377 ms 11208 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4584 KB Output is correct
3 Correct 6 ms 4660 KB Output is correct
4 Correct 6 ms 4660 KB Output is correct
5 Correct 9 ms 4660 KB Output is correct
6 Correct 6 ms 4660 KB Output is correct
7 Incorrect 6 ms 4660 KB Output isn't correct
8 Halted 0 ms 0 KB -