Submission #1481444


Source Code Expand

#include <bits/stdc++.h>

const int N = 1e9 + 100;
const int M = 1e5 + 100;
const int MOD = 1e9 + 7;

int n, m;
int a[M];

struct Matrix {
	int x[3][3];

	void reset() {
		std::memset(x, 0, sizeof(x));
	}

	void setI() {
		std::memset(x, 0, sizeof(x));
		x[0][0] = x[1][1] = x[2][2] = 1;
	}

	void add(int r, int c, int delta) {
		x[r][c] += delta;
	}

	friend Matrix operator * (const Matrix &a, const Matrix &b) {
		Matrix result;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				result.x[i][j] = 0;
				for (int k = 0; k < 3; k++) {
					result.x[i][j] += (long long)a.x[i][k] * b.x[k][j] % MOD;
					result.x[i][j] %= MOD;
				}
			}
		}
		return result;
	}

	friend Matrix operator ^ (Matrix a, int b) {
		Matrix result;
		result.reset();
		for (int i = 0; i < 3; i++) {
			result.x[i][i] = 1;
		}
		for ( ; b; b >>= 1) {
			if (b & 1) {
				result = result * a;
			}
			a = a * a;
		}
		return result;
	}
};

void init() {
	std::cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}
}

void work() {
	static Matrix trans[2];
	static Matrix mat;

	mat.setI();
	trans[0].reset();
	trans[1].reset();

	// 0
	// empty
	trans[0].add(0, 0, 1);
	trans[0].add(1, 1, 1);
	trans[0].add(2, 2, 1);
	// cut
	trans[0].add(2, 0, 1);
	// cut - ball
	trans[0].add(2, 1, 2);
	// cut - ball - ball
	trans[0].add(2, 2, 1);
	// ball
	trans[0].add(0, 1, 2);
	trans[0].add(1, 2, 1);
	// ball - ball
	trans[0].add(0, 2, 1);

	// 1
	// empty
	trans[1].add(0, 0, 1);
	trans[1].add(1, 1, 1);
	trans[1].add(2, 2, 1);
	// ball
	trans[1].add(0, 1, 2);
	trans[1].add(1, 2, 1);
	// ball - ball
	trans[1].add(0, 2, 1);

	int cur = 1;
	for (int i = 1; i <= m; i++) {
		mat = mat * (trans[0] ^ (a[i] - cur));
		mat = mat * trans[1];
		cur = a[i] + 1;
	}
	mat = mat * (trans[0] ^ (n - cur));

	long long answer = 1LL * mat.x[0][2] + 2LL * mat.x[1][2] + 1LL * mat.x[2][2];
	std::cout << answer % MOD << std::endl;
}

int main() {
	init();
	work();

	return 0;
}

Submission Info

Submission Time
Task E - Placing Squares
User SpoiledInnocence
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2085 Byte
Status AC
Exec Time 240 ms
Memory 640 KB

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:59:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 38
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 77 ms 384 KB
subtask_1_02.txt AC 20 ms 256 KB
subtask_1_03.txt AC 9 ms 384 KB
subtask_1_04.txt AC 21 ms 512 KB
subtask_1_05.txt AC 240 ms 640 KB
subtask_1_06.txt AC 239 ms 640 KB
subtask_1_07.txt AC 34 ms 640 KB
subtask_1_08.txt AC 34 ms 640 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 2 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 11 ms 384 KB
subtask_1_18.txt AC 25 ms 512 KB
subtask_1_19.txt AC 1 ms 256 KB
subtask_1_20.txt AC 31 ms 640 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