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
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 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