oj.uz

Submission #313222

# Submission time Handle Problem Language Result Execution time Memory
313222 2020-10-15T14:23:29 Z CaroLinda Semafor (COI20_semafor) C++14
18 / 100
 426 ms 524292 KB 
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a; i < b; i++ )
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define ll long long 
#define ff first
#define ss second
#define all(x) x.begin(),x.end()

const ll MOD = 1e9+7 ;

using namespace std ;

struct Matrix
{

	vector< vector<ll> > vec ;

	Matrix(int n = 0)
	{
		vec.resize(n, vector<ll>(n,0) ) ;
	}

	Matrix operator * (Matrix other) const
	{
		int n = sz(vec) ;

		Matrix newMatrix(n) ;

		for(int i = 0 ; i < n ; i++ )
			for(int j = 0 ; j < n ; j++ )
				for(int g = 0 ; g < n ; g++ )
				{
					ll toSum = vec[i][g] * other.vec[g][j] ;
					toSum %= MOD ;

					newMatrix.vec[i][j] += toSum ;
					if(newMatrix.vec[i][j] >= MOD ) newMatrix.vec[i][j] -= MOD ;

				}

		return newMatrix ;
	}

} ;

int m , n , k , x ;
int myMask[10] = {10,2, 1+8, 1+2+4, 16+2, 1+16+4, 8+4, 1+2, 31-2, 31-8 } ;
int matDiff[120][120] ;

bool isOn(int i, int m) { return ((1<<i)&m) != 0 ; }

Matrix expo(Matrix x, ll num )
{
	if(num == 1) return x ;

	Matrix aux = expo(x, num>>1LL ) ;
	aux = aux*aux ;

	if(num&1) aux = aux*x ;

	return aux ;
}

int main()
{
	/*for(int i = 0 ; i < 10 ; i++ )
	{
		debug("Sobre %d: " , i  );
		for(int j = 0 ; j < 5 ; j++ ) debug("%d", isOn(j, myMask[i])) ;
		debug("\n") ;
	}*/
	scanf("%d%d%d%d", &m, &n, &k , &x ) ;

	int lim = (m == 1) ? 6 : 11 ;
	Matrix findK(lim) ;
	Matrix findR(lim) ;
		
	for(int diff = 0 ; diff < lim ; diff++ )
	{
		if(diff)
			findK.vec[diff-1][diff] = diff ;

		if(diff+1 < lim)
			findK.vec[diff+1][diff] = lim-1-diff ;

	}

	/*debug("Printing findK without exponentiating\n") ;
	for(int i = 0 ; i < lim ; i++ , debug("\n"))
		for(int j = 0 ; j < lim ; j++ ) debug("%lld " , findK.vec[i][j] ) ; */

	Matrix base(lim) ;
	base.vec[0][0] = 1 ;

	if(n%k) findR = base * expo( findK, n%k ) ;
	findK = base*expo(findK, k);

	/*debug("Printing findK with exponentiating\n") ;
	for(int i = 0 ; i < lim ; i++, debug("\n"))
		for(int j = 0 ; j < lim ; j++ ) debug("%lld " , findK.vec[i][j] ) ; */

	/*debug("Printing findR with exponentiating\n") ;
	for(int i = 0 ; i < lim ; i++, debug("\n"))
		for(int j = 0 ; j < lim ; j++ ) debug("%lld " , findR.vec[i][j] ) ; */

	lim = (m == 1) ? 10 : 100 ;

	Matrix findDp(lim) ;

	for(int i = 0 ; i < lim ; i++)
		for(int j = 0 ; j < lim ; j++ )
		{
			int bitmask1 = (myMask[i/10] << 5) + myMask[i%10] ;
			int bitmask2 = (myMask[j/10] << 5) + myMask[j%10] ;
			int diff = 0 ;

			for(int g = 0 ; g < 10 ; g++ )
				diff += (isOn(g,bitmask1) != isOn(g, bitmask2)) ;

			findDp.vec[i][j] = findK.vec[0][diff] ;
			matDiff[i][j] = diff ;

		}

	/*debug("Printing graph\n") ;
	for(int i = 0 ; i < lim ; i++ , debug("\n"))
		for(int j = 0 ; j < lim ; j++ ) debug("%lld " , findDp.vec[i][j]);*/

	findDp = expo( findDp, n/k ) ;

	/*debug("Printing findDp after exponentiating\n") ;
	for(int i = 0 ; i < lim ; i++ , debug("\n"))
		for(int j = 0 ; j < lim ; j++ ) debug("%lld " , findDp.vec[i][j]);*/
 
	vector<ll> dp(lim+1,0LL) ;

	for(int i = 0 ; i < lim ; i++ ) 
	{
		if( n%k == 0 )
		{
			dp[i] = findDp.vec[x][i] ;
			continue ;
		}

		for(int g = 0 ; g < lim ; g++ )
		{
			ll toSum = findDp.vec[x][g] * findR.vec[0][ matDiff[i][g] ] ;
			dp[i] += toSum % MOD ;

			if( dp[i] >= MOD ) dp[i] -= MOD;
		}
	}

	for(int i = 0 ; i<lim ; i++ ) printf("%lld\n" , dp[i] ) ;

}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Runtime error 426 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1408 KB Output is correct
2 Correct 165 ms 2688 KB Output is correct
3 Runtime error 391 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1408 KB Output is correct
2 Correct 165 ms 2688 KB Output is correct
3 Runtime error 391 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 55 ms 1408 KB Output is correct
11 Correct 165 ms 2688 KB Output is correct
12 Runtime error 391 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -