Submission #78132

#	Time	Username	Problem	Language	Result	Execution time	Memory
78132		igzi	Fibonacci representations (CEOI18_fib)	C++17	50 / 100	4081 ms	1112 KiB

fib

#include <bits/stdc++.h>
#define mod 1000000007
#define maxN 100005

using namespace std;

vector <int> v,u;
int n,a,i;

bool moze(int y){
    if(v[y]<=2) return false;
    if(y==0) return true;
    if(v[y-1]==v[y]-1) return false;
    if(v[y-1]!=v[y]-2) return true;
    return moze(y-1);
}

void ubaci1(int x){
    int i,y;
    y=lower_bound(v.begin(),v.end(),x)-v.begin();
    v.insert(v.begin()+y,x);
    for(i=v.size()-1;i>0;i--){
     if(i>=v.size()) continue;
      if(v[i]==v[i-1]){
          int tmp=v[i];
          v.erase(v.begin()+i);
          y=lower_bound(v.begin(),v.end(),tmp-1)-v.begin();
          v.insert(v.begin()+y,tmp-1);
          y=lower_bound(v.begin(),v.end(),max(tmp-2,1))-v.begin();
          v.insert(v.begin()+y,max(tmp-2,1));
          i+=2;
      }
    }
}

void ubaci(int x){
    int y=lower_bound(v.begin(),v.end(),x)-v.begin();
    if(moze(y)){
        ubaci1(x);
        return;
    }
    if(x>1){
    int i;
    if(v[y]!=x) {v.insert(v.begin()+y,x); return;}
    v.erase(v.begin()+y);
    ubaci(max(1,x-2));
    ubaci(x+1);}
    else{
        if(v.size() && v[0]==1) {v.erase(v.begin()); ubaci(2);}
        else v.insert(v.begin(),1);
    }
}

long long resi(){
    long long i,j,x,a,ans,tmp,pom,ans1;
    ans=1;
    ans1=0;
    a=0;
    for(i=0;i<v.size();i++){
        pom=ans;
        x=v[i]-a-1;
        x=(x/2+1);
        ans*=x;
        if(a%2==v[i]%2) ans+=ans1;
        ans%=mod;
        x=v[i]-a-3;
        if(x>=0){
            tmp=ans1;
            x=(x/2+1);
            ans1=pom*x;
            if(a%2==v[i]%2) ans1+=tmp;
            ans1%=mod;
        }
        if(v[i]==a+1) ans1=0;
        a=v[i];
        //cout<<ans<<" "<<ans1<<endl;
    }
    return (ans+mod)%mod;
}

int main() {
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a;
        int y=lower_bound(v.begin(),v.end(),a)-v.begin();
        //cout<<y<<endl;
        if(y==v.size() || v[y]!=a) v.insert(v.begin()+y,a);
        else{
        if(moze(y)) ubaci1(a);
        else ubaci(a);
        }
        //for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
        for(int k=v.size();k>=0;k--){
        for(int j=v.size()-1;j>0;j--){
            if(v[j]-1==v[j-1] && (j==v.size()-1 || v[j]!=v[j+1]-1)){
          v.insert(v.begin()+j+1,v[j]+1);
          v.erase(v.begin()+j-1);
          v.erase(v.begin()+j-1);
        }
        }
        }
        cout<<resi()<<endl;
    }
    return 0;
}

Compilation message (stderr)

fib.cpp: In function 'void ubaci1(int)':
fib.cpp:23:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(i>=v.size()) continue;
         ~^~~~~~~~~~
fib.cpp: In function 'void ubaci(int)':
fib.cpp:43:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^
fib.cpp: In function 'long long int resi()':
fib.cpp:59:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~
fib.cpp:55:17: warning: unused variable 'j' [-Wunused-variable]
     long long i,j,x,a,ans,tmp,pom,ans1;
                 ^
fib.cpp: In function 'int main()':
fib.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(y==v.size() || v[y]!=a) v.insert(v.begin()+y,a);
            ~^~~~~~~~~~
fib.cpp:95:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(v[j]-1==v[j-1] && (j==v.size()-1 || v[j]!=v[j+1]-1)){
                                   ~^~~~~~~~~~~~

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