Submission #1517777
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pp; typedef pair<ll,ll> pll; void read(int& x){ scanf("%d",&x); } void read(ll& x){ scanf("%lld",&x); } template<typename T,typename... Args> void read(T& a,Args&... b){ read(a); read(b...); } #define all(x) (x).begin(),(x).end() #define pb push_back #define eb emplace_back #define x first #define y second int n, m; const ll M = ll(1e9)+7; struct Mat { ll a[3][3]; Mat(){ memset(a, 0, sizeof(a)); } Mat operator*(Mat r){ Mat ret; for(int i=0; i<3; ++i){ for(int j=0; j<3; ++j){ for(int k=0; k<3; ++k){ ret.a[i][j] += a[i][k] * r.a[k][j] % M; ret.a[i][j] %= M; } } } return ret; } }; Mat yes, no, I; void mat(){ yes.a[0][0] = 1; yes.a[0][2] = 1; yes.a[1][0] = 1; yes.a[1][1] = 1; yes.a[1][2] = 1; yes.a[2][0] = 1; yes.a[2][1] = 2; yes.a[2][2] = 2; no.a[0][0] = 1; no.a[1][0] = 1; no.a[1][1] = 1; no.a[2][0] = 1; no.a[2][1] = 2; no.a[2][2] = 1; for(int i=0; i<3; ++i) I.a[i][i]=1; } Mat Pow(Mat base, int e){ if(e == 0) return I; Mat ret = Pow(base, e/2); ret = ret*ret; if(e&1) ret = ret*base; return ret; } int main() { read(n, m); mat(); int lp=0; Mat x = I; for(int i=1; i<=m; ++i){ int p; read(p); x = no * x; x = Pow(yes, p-lp-1) * x; lp = p; } x = no * x; x = Pow(yes, n-lp-1) * x; printf("%lld\n", x.a[2][0]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Placing Squares |
User | Namnamseo |
Language | C++14 (GCC 5.4.1) |
Score | 1600 |
Code Size | 1487 Byte |
Status | AC |
Exec Time | 294 ms |
Memory | 256 KB |
Compile Error
./Main.cpp: In function ‘void read(int&)’: ./Main.cpp:6:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] void read(int& x){ scanf("%d",&x); } ^ ./Main.cpp: In function ‘void read(ll&)’: ./Main.cpp:7:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] void read(ll& x){ scanf("%lld",&x); } ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 1600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
sample_04.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 94 ms | 256 KB |
subtask_1_02.txt | AC | 24 ms | 256 KB |
subtask_1_03.txt | AC | 10 ms | 256 KB |
subtask_1_04.txt | AC | 24 ms | 256 KB |
subtask_1_05.txt | AC | 294 ms | 256 KB |
subtask_1_06.txt | AC | 294 ms | 256 KB |
subtask_1_07.txt | AC | 39 ms | 256 KB |
subtask_1_08.txt | AC | 39 ms | 256 KB |
subtask_1_09.txt | AC | 4 ms | 256 KB |
subtask_1_10.txt | AC | 3 ms | 256 KB |
subtask_1_11.txt | AC | 2 ms | 256 KB |
subtask_1_12.txt | AC | 1 ms | 256 KB |
subtask_1_13.txt | AC | 2 ms | 256 KB |
subtask_1_14.txt | AC | 3 ms | 256 KB |
subtask_1_15.txt | AC | 1 ms | 256 KB |
subtask_1_16.txt | AC | 1 ms | 256 KB |
subtask_1_17.txt | AC | 13 ms | 256 KB |
subtask_1_18.txt | AC | 29 ms | 256 KB |
subtask_1_19.txt | AC | 1 ms | 256 KB |
subtask_1_20.txt | AC | 35 ms | 256 KB |
subtask_1_21.txt | AC | 1 ms | 256 KB |
subtask_1_22.txt | AC | 1 ms | 256 KB |
subtask_1_23.txt | AC | 1 ms | 256 KB |
subtask_1_24.txt | AC | 1 ms | 256 KB |
subtask_1_25.txt | AC | 1 ms | 256 KB |
subtask_1_26.txt | AC | 1 ms | 256 KB |
subtask_1_27.txt | AC | 1 ms | 256 KB |
subtask_1_28.txt | AC | 1 ms | 256 KB |
subtask_1_29.txt | AC | 1 ms | 256 KB |
subtask_1_30.txt | AC | 1 ms | 256 KB |