oj.uz

Submission #71937

# Submission time Handle Problem Language Result Execution time Memory
71937 2018-08-26T01:38:52 Z 블랙야크(#2261, cki86201) Cross on the Grid (FXCUP3_cross) C++17
100 / 100
 4 ms 820 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

const int MOD = 1e9 + 7;
const int L = 16;

struct mat {
	int p[L][L];
	mat operator*(mat A) {
		mat res;
		rep(a, L) rep(b, L) res.p[a][b] = 0;
		rep(a, L) rep(c, L) rep(b, L) if(p[a][c] && A.p[c][b]) res.p[a][b] = (res.p[a][b] + p[a][c] * (ll)A.p[c][b]) % MOD;
		return res;
	}
};

int chk(int x) {
	int a = x & 3, b = (x >> 2) & 3;
	if(a && b && abs(a - b) <= 1) return 0;
	return 1;
}

int main() {
	mat X, R;
	rep(i, L) rep(j, L) X.p[i][j] = 0;
	rep(i, L) rep(j, L) if(chk(i) && chk(j) && (i & 3) == ((j >> 2) & 3) && ((j & 3) == 0 || ((i >> 2) & 3) != (j & 3))) X.p[i][j] = 1;
	rep(i, L) rep(j, L) R.p[i][j] = (i == j ? 1 : 0);
	int N; scanf("%d", &N); N -= 2;
	while(N) {
		if(N & 1) R = R * X;
		X = X * X;
		N >>= 1;
	}
	ll ans = 0;
	rep(i, L) ans = (ans + R.p[0][i]) % MOD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 4 ms 664 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 4 ms 664 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 3 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 2 ms 664 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 3 ms 720 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 4 ms 664 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 3 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 2 ms 664 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 3 ms 720 KB Output is correct
17 Correct 3 ms 720 KB Output is correct
18 Correct 3 ms 780 KB Output is correct
19 Correct 3 ms 780 KB Output is correct
20 Correct 3 ms 788 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 3 ms 796 KB Output is correct
23 Correct 2 ms 796 KB Output is correct
24 Correct 2 ms 796 KB Output is correct
25 Correct 4 ms 820 KB Output is correct