# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133896 | 2019-07-21T16:38:21 Z | sebinkim | Fibonacci representations (CEOI18_fib) | C++14 | 4000 ms | 1788 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <ll, ll> pll; const ll mod = 1e9 + 7; set <pll> S; ll n; void erase(set <pll>::iterator it) { S.erase(it); } void insert(pll p) { S.insert(p); } void insert(ll t, ll x) { auto it = S.lower_bound(pll(x, 2e9)); if(it == S.begin() || prev(it) -> second < x){ pll p(x - 1, x + 1); if(it != S.begin() && prev(it) -> second + 1 == x){ p.first = prev(it) -> first; erase(prev(it)); } it = S.lower_bound(pll(x, 2e9)); if(it != S.end() && x + 1 == it -> first){ p.second = it -> second; erase(it); } insert(p); } else{ it = prev(it); if(it -> second - x & 1){ pll p(it -> first + 1, x); ll x1 = it -> first - 1, x2 = it -> second; erase(it); if(p.first < p.second) insert(p); if(x1 >= 0) insert(t, max(x1, 1ll)); insert(t, x2); } else{ pll p(it -> first, min(it -> second - 2, x)); x = max(it -> second, x + 1); erase(it); if(p.first < p.second) insert(p); insert(t, x); } } } int main() { ll i, x; ll d0, d1, lt, _d0, _d1, d, l; scanf("%lld", &n); for(i=0; i<n; i++){ scanf("%lld", &x); insert(i, x); // for(pll t: S) printf("[%lld %lld] ", t.first, t.second); puts(""); d0 = 0; d1 = 1; lt = 0; for(pll t: S){ d = t.first + 1 - lt; l = (t.second - t.first) / 2; _d0 = (d / 2 * d0 + (d - 1) / 2 * d1) % mod; _d1 = (d0 + d1 + _d0 * (l - 1)) % mod; d0 = _d0; d1 = _d1; lt = t.second - 1; } printf("%lld\n", (d0 + d1) % mod); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
19 | Correct | 6 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 256 KB | Output is correct |
21 | Correct | 3 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 256 KB | Output is correct |
23 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Execution timed out | 4016 ms | 1788 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
19 | Correct | 6 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 256 KB | Output is correct |
21 | Correct | 3 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 256 KB | Output is correct |
23 | Correct | 2 ms | 256 KB | Output is correct |
24 | Correct | 2 ms | 376 KB | Output is correct |
25 | Execution timed out | 4016 ms | 1788 KB | Time limit exceeded |
26 | Halted | 0 ms | 0 KB | - |