Submission #1072859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072859		kunzaZa183	Fibonacci representations (CEOI18_fib)	C++17	25 / 100	337 ms	262144 KiB

fib

  #include <bits/stdc++.h>
  using namespace std;

  void add(set<int> &si, int x) {
    queue<int> qi;
    qi.push(x);
    while(!qi.empty()) {
      int tmp = qi.front();
      qi.pop();
      if(si.count(tmp)) {
        si.erase(tmp);
        if(tmp==1) {
          qi.push(2);
        } else if(tmp==2) {
          qi.push(1);
          qi.push(3);
        } else {
          qi.push(tmp-2);
          qi.push(tmp + 1);
        }
        continue;
      } else if(si.count(tmp + 1)) {
        si.erase(tmp + 1);
        qi.push(tmp + 2);
      } else if(si.count(tmp - 1)) {
        si.erase(tmp - 1);
        qi.push(tmp + 1);
      } else {
        si.insert(tmp);
      }
    }
  }

  const int mod = 1e9+7;

  map<int,map<set<int>,int>> msii;

  int state(set<int> vi, int cur) {
    if(vi.empty())
      return 1;
    int x = *vi.rbegin();
    cur = min(cur,x);

    if(msii[cur].count(vi))
      return msii[cur][vi];
    auto it = &msii[cur][vi];
    int total = 0;
    vi.erase(x);
    if( x <=cur) {
      
      total += state(vi,x - 1);
    }
    if(x - 1<=cur && x>2)
    {
      add(vi, x - 2);
      total += state(vi,x - 2);
    }
    vi.insert(x);
    *it = total%mod;
    // if(x==2 && cur==4) {
    //    cout<<"TOTAL = "<<total<<'\n'; 
    //   }
    return total % mod;
  }

  int32_t main() {
    int n;
    cin>>n;
    vector<int> vi(n);
    
    for(auto &a:vi)
      cin>>a;
    
    set<int> cur;
    for(auto a:vi) {
      add(cur,a);
      
      // cout<<"CUR\n";
      // for(auto a:cur)
      //   cout<<a<<' ';
      // cout<<"\n";

      cout<<state(cur, 1e10)<<"\n";
    }
  }

Compilation message (stderr)

fib.cpp: In function 'int32_t main()':
fib.cpp:83:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
   83 |       cout<<state(cur, 1e10)<<"\n";
      |                        ^~~~

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