oj.uz

Submission #78132

# Submission time Handle Problem Language Result Execution time Memory
78132 2018-10-02T14:35:06 Z igzi Fibonacci representations (CEOI18_fib) C++17
50 / 100
 4000 ms 1112 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 672 KB Output is correct
12 Correct 2 ms 672 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 3 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 672 KB Output is correct
12 Correct 2 ms 672 KB Output is correct
13 Correct 2 ms 672 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct
17 Correct 3 ms 672 KB Output is correct
18 Correct 3 ms 672 KB Output is correct
19 Correct 2 ms 672 KB Output is correct
20 Correct 3 ms 672 KB Output is correct
21 Correct 3 ms 760 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 760 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 672 KB Output is correct
12 Correct 2 ms 672 KB Output is correct
13 Correct 2 ms 672 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 2 ms 672 KB Output is correct
16 Correct 2 ms 672 KB Output is correct
17 Correct 3 ms 672 KB Output is correct
18 Correct 3 ms 672 KB Output is correct
19 Correct 2 ms 672 KB Output is correct
20 Correct 3 ms 672 KB Output is correct
21 Correct 3 ms 760 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 760 KB Output is correct
24 Correct 3 ms 760 KB Output is correct
25 Execution timed out 4081 ms 1112 KB Time limit exceeded
26 Halted 0 ms 0 KB -