Submission #287608

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
287608	2020-08-31 21:08:31	TadijaSebez	Fibonacci representations (CEOI18_fib)	C++11	50 / 100	2927 ms	262148 KiB

fib

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
#define matrix vector<vector<int>>
matrix operator * (matrix a,matrix b){
  matrix ans(2,vector<int>(2,0));
  for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
      for(int k=0;k<2;++k)
        ans[i][j]=add(ans[i][j],mul(a[i][k],b[k][j]));
  return ans;
}
matrix build(int sz){
  return {{1,1},{(sz-1)/2,sz/2}};
}
const int N=100050;
const int M=30*N*2;
const int lim=1e9+1000;
int ls[M],rs[M],tsz,root;
matrix idx,seg[M];
void Set(int&c,int ss,int se,int qi,matrix m){
  if(!c)c=++tsz,seg[c]=idx;
  if(ss==se){seg[c]=m;return;}
  int mid=ss+se>>1;
  if(qi<=mid)Set(ls[c],ss,mid,qi,m);
  else Set(rs[c],mid+1,se,qi,m);
  seg[c]=seg[rs[c]]*seg[ls[c]];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

fib.cpp: In function 'void Set(int&, int, int, int, std::vector<std::vector<int> >)':
fib.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid=ss+se>>1;
      |          ~~^~~
fib.cpp: In function 'int main()':
fib.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%i",&a);
      |   ~~~~~^~~~~~~~~

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