oj.uz

Submission #71861

# Submission time Handle Problem Language Result Execution time Memory
71861 2018-08-25T17:29:36 Z 비타오백(#2241, junodeveloper) Cross on the Grid (FXCUP3_cross) C++17
100 / 100
 3 ms 628 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> VL;
typedef vector<VL> VVL;
const int MOD = 1e9 + 7;
VVL mul(VVL& a, VVL& b) {
	VVL c(12, VL(12));
	for(int i=0; i<12; i++) for(int j=0; j<12; j++)
		for(int k=0; k<12; k++) c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j] % MOD) % MOD;
	return c;
}
VVL Pow(VVL a, int pw) {
	VVL b = a, r(12, VL(12));
	for(int i=0; i<12; i++) r[i][i] = 1;
	while(pw > 0) {
		if(pw & 1) r = mul(r, b);
		b = mul(b, b);
		pw >>= 1;
	}
	return r;
}
int in[12][12]={
	{1,1,1,1,0,0,0,0,0,0,0,0},
	{0,0,0,0,1,0,1,1,1,1,1,0},
	{0,0,0,0,0,1,0,1,1,1,1,1},
	{0,0,0,0,1,1,1,0,1,0,1,1},
	{1,0,0,0,0,0,0,0,0,0,0,0},
	{0,1,0,0,0,0,0,0,0,0,0,0},
	{0,0,1,0,0,0,0,0,0,0,0,0},
	{0,0,0,1,0,0,0,0,0,0,0,0},
	{0,0,0,0,1,0,0,0,0,0,0,0},
	{0,0,0,0,0,1,0,0,0,0,0,0},
	{0,0,0,0,0,0,1,0,0,0,0,0},
	{0,0,0,0,0,0,0,1,0,0,0,0}
};
int a[12]={1,1,1,1,1,0,0,0,1,0,0,0};
int main() {
	VVL init(12,VL(12));
	for(int i=0; i<12; i++) for(int j=0; j<12; j++) init[i][j]=in[i][j];
	int n;
	scanf("%d", &n);
	VVL mat = Pow(init, n-3);
	int res = 0;
	for(int i=0; i<4; i++) {
		int val = 0;
		for(int j=0; j<12; j++) val = (val + 1ll * mat[i][j] * a[j] % MOD) % MOD;
		res = (res + val) % MOD;
	}
	printf("%d", res);
	return 0;
}

Compilation message

cross.cpp: In function 'int main()':
cross.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 524 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 3 ms 532 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 524 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 3 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 2 ms 532 KB Output is correct
12 Correct 2 ms 532 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 3 ms 592 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 524 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 3 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 2 ms 532 KB Output is correct
12 Correct 2 ms 532 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 3 ms 592 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 3 ms 604 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 3 ms 628 KB Output is correct
24 Correct 2 ms 628 KB Output is correct
25 Correct 3 ms 628 KB Output is correct