Submission #1909185
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>
#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
struct matrix{ LL mat[5][5]; }g, g0, ans;
matrix operator*(matrix a, matrix b)
{
matrix tmp; memset(tmp.mat, 0, sizeof(tmp.mat));
Rep0(i, 3) Rep0(j, 3) Rep0(k, 3) tmp.mat[i][j] = (tmp.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
return tmp;
}
void qpow(matrix &a, int k)
{
matrix tmp; memset(tmp.mat, 0, sizeof(tmp.mat));
Rep0(i, 3) tmp.mat[i][i] = 1;
while (k){
if (k & 1) tmp = tmp * a;
a = a * a, k >>= 1;
}
a = tmp;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int la = 0;
ans.mat[0][0] = 1;
g0.mat[3][3] = 1;
g0.mat[1][3] = 1, g0.mat[1][1] = 1;
g0.mat[2][3] = 1, g0.mat[2][2] = 1;
g0.mat[0][0] = 1, g0.mat[0][1] = 1, g0.mat[0][2] = 1, g0.mat[0][3] = 1;
Rep(i, m + 1) {
int x;
if (i <= m) scanf("%d", &x);
else x = n + 1;
memset(g.mat, 0, sizeof(g.mat));
g.mat[3][0] = 1, g.mat[3][3] = 1;
g.mat[1][0] = 1, g.mat[1][1] = 1, g.mat[1][3] = 1;
g.mat[2][0] = 1, g.mat[2][2] = 1, g.mat[2][3] = 1;
g.mat[0][3] = 1, g.mat[0][1] = 1, g.mat[0][2] = 1, g.mat[0][0] = 2;
qpow(g, x - la - 1);
ans = ans * g;
if (i <= m) ans = ans * g0;
la = x;
}
printf("%d\n", ans.mat[0][3]);
return 0;
}
Submission Info
Submission Time
2017-12-25 17:55:27+0900
Task
E - Placing Squares
User
dujvet
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
1614 Byte
Status
AC
Exec Time
512 ms
Memory
128 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:61:30: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘LL {aka long long int}’ [-Wformat=]
printf("%d\n", ans.mat[0][3]);
^
./Main.cpp:39:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:48:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
if (i <= m) scanf("%d", &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
128 KB
sample_02.txt
AC
1 ms
128 KB
sample_03.txt
AC
1 ms
128 KB
sample_04.txt
AC
1 ms
128 KB
subtask_1_01.txt
AC
162 ms
128 KB
subtask_1_02.txt
AC
41 ms
128 KB
subtask_1_03.txt
AC
15 ms
128 KB
subtask_1_04.txt
AC
39 ms
128 KB
subtask_1_05.txt
AC
512 ms
128 KB
subtask_1_06.txt
AC
511 ms
128 KB
subtask_1_07.txt
AC
64 ms
128 KB
subtask_1_08.txt
AC
64 ms
128 KB
subtask_1_09.txt
AC
6 ms
128 KB
subtask_1_10.txt
AC
4 ms
128 KB
subtask_1_11.txt
AC
1 ms
128 KB
subtask_1_12.txt
AC
1 ms
128 KB
subtask_1_13.txt
AC
2 ms
128 KB
subtask_1_14.txt
AC
3 ms
128 KB
subtask_1_15.txt
AC
1 ms
128 KB
subtask_1_16.txt
AC
1 ms
128 KB
subtask_1_17.txt
AC
21 ms
128 KB
subtask_1_18.txt
AC
49 ms
128 KB
subtask_1_19.txt
AC
1 ms
128 KB
subtask_1_20.txt
AC
60 ms
128 KB
subtask_1_21.txt
AC
1 ms
128 KB
subtask_1_22.txt
AC
1 ms
128 KB
subtask_1_23.txt
AC
1 ms
128 KB
subtask_1_24.txt
AC
1 ms
128 KB
subtask_1_25.txt
AC
1 ms
128 KB
subtask_1_26.txt
AC
1 ms
128 KB
subtask_1_27.txt
AC
1 ms
128 KB
subtask_1_28.txt
AC
1 ms
128 KB
subtask_1_29.txt
AC
1 ms
128 KB
subtask_1_30.txt
AC
1 ms
128 KB