oj.uz

Submission #1072859

# Submission time Handle Problem Language Result Execution time Memory
1072859 2024-08-24T05:55:49 Z kunzaZa183 Fibonacci representations (CEOI18_fib) C++17
25 / 100
 337 ms 262144 KB 
  #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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 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 436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 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 436 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 12 ms 4188 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 12 ms 4188 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7392 KB Output is correct
2 Runtime error 304 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 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 436 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 12 ms 4188 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 12 ms 4188 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 21 ms 7392 KB Output is correct
14 Runtime error 304 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 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 436 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 12 ms 4188 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 12 ms 4188 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 21 ms 7392 KB Output is correct
14 Runtime error 304 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -