oj.uz

Submission #313255

# Submission time Handle Problem Language Result Execution time Memory
313255 2020-10-15T15:55:52 Z CaroLinda Semafor (COI20_semafor) C++14
18 / 100
 161 ms 2688 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 ) ;

	assert(n >= 0) ;

	if(n == 0)
	{
		int lim = (m==1) ? 10 : 100 ;
		for(int i = 0 ; i < lim ; i++ ) printf("%d\n", i == x ? 1 : 0) ;
		return 0 ;
	}

	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) > 0 ) 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]);*/

	vector<ll> dp(lim+1,0LL) ;

	if( k > n )
	{	
		for(int i= 0 ; i < lim ; i++ )
			dp[i] = findR.vec[0][ matDiff[i][x] ] ;
	}
	else 
	{
		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]);*/

		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 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 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 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 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 1 ms 512 KB Execution killed with signal 11 (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 58 ms 1408 KB Output is correct
2 Correct 161 ms 2688 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (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 58 ms 1408 KB Output is correct
2 Correct 161 ms 2688 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11 (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 58 ms 1408 KB Output is correct
11 Correct 161 ms 2688 KB Output is correct
12 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -